# Algoritmo de Euclides estendido (ax + by = mdc(a, b))

Resolve a identidade de Bézout a·x + b·y = mdc(a, b) para inteiros de qualquer sinal: entrega a tabela completa de passos de divisão (cada linha satisfaz r = a·s + b·t), o mdc e o mmc. Com o lado direito opcional c, torna-se um solucionador de equações diofantinas: se mdc | c dá a solução particular e a geral x = x₀ + (b/g)t; caso contrário, informa claramente que não há solução inteira. Clássico: 240 × (−9) + 46 × 47 = 2.

> Página canônica: https://elysiatools.com/pt/tools/extended-euclidean-algorithm

- **Categoria:** Math & Numbers

- **Palavras-chave:** euclides estendido, identidade de bézout, coeficientes de bézout, mdc, equação diofantina, diofantina linear, teoria dos números

## Visão geral

Esta ferramenta calcula o Algoritmo de Euclides Estendido para dois números inteiros com qualquer sinal, determinando o MDC, o MMC e os coeficientes da Identidade de Bézout. Além disso, permite resolver equações diofantinas lineares na forma ax + by = c, fornecendo a solução particular e a equação geral.

## Entradas

- **Valor a** (text): First integer; negative values are supported.
- **Valor b** (text): Second integer; negative values are supported.
- **Lado direito c (opcional, resolve ax + by = c)** (text): Optional target: solves ax + by = c when gcd(a, b) divides c.
- **Estilo de saída** (select)

## Quando usar

- Quando você precisa encontrar os coeficientes inteiros de Bézout (x e y) tais que a·x + b·y = mdc(a, b).
- Ao resolver equações diofantinas lineares ax + by = c e verificar se existem soluções inteiras.
- Durante o estudo ou ensino de teoria dos números, criptografia e aritmética modular para acompanhar os passos de divisão.

## Como funciona

- Informe os valores inteiros para 'a' e 'b', com a opção de adicionar o valor 'c' para equações diofantinas.
- Selecione o estilo de saída desejado: ver apenas o resultado final ou a tabela detalhada com os passos de divisão.
- O algoritmo processa as divisões sucessivas mantendo a relação de resto r = a·s + b·t até atingir o resto zero.
- A ferramenta exibe o MDC, MMC, a identidade de Bézout e a solução geral paramétrica se 'c' for informado.

## Casos de uso

- Cálculo de inversos modulares em problemas de criptografia como RSA.
- Resolução de problemas de divisibilidade e equações diofantinas em disciplinas de matemática e computação.
- Conferência passo a passo de exercícios acadêmicos sobre o Algoritmo de Euclides Estendido.

## Perguntas frequentes

### O que acontece se o valor c não for divisível pelo MDC de a e b?

A ferramenta indicará claramente que não existem soluções inteiras para a equação diofantina linear.

### A ferramenta aceita números inteiros negativos?

Sim, você pode inserir inteiros positivos ou negativos nos campos a, b e c.

### Como o MMC é calculado?

O MMC é obtido diretamente a partir da relação |a × b| / mdc(a, b).

### Qual a diferença entre a saída de resultado e a de passos?

A opção de passos exibe a tabela completa de divisões e substituições, enquanto a opção de resultado foca nas respostas finais e verificação.

### O que representa a variável t na solução geral?

A variável t representa qualquer número inteiro pertencente a ℤ, gerando a família infinita de soluções inteiras.

## Ferramentas relacionadas

- [Simplificador de álgebra booleana (mapa de Karnaugh)](https://elysiatools.com/pt/tools/boolean-algebra-simplifier): Simplifica funções booleanas para a SOP mínima: introduza uma expressão (A–D, + OU, · E, ' NÃO, ≤ 4 variáveis) ou a lista de minterms Σm; o algoritmo de Quine-McCluskey obtém os implicantes primos, toma os essenciais e completa uma cobertura mínima exata; são exibidos a SOP mínima, o mapa de Karnaugh em código Gray (2–4 variáveis), a forma canônica Σm e uma verificação sobre todas as atribuições. Clássicos: AB + A'B → B; Σm(0,1,2,4,5,6) (3 variáveis) → B' + C'.
- [Conversor de Razão de Diluição (1:X ↔ 1/X ↔ %)](https://elysiatools.com/pt/tools/dilution-ratio-converter): Converte entre as notações de diluição de laboratório: proporção 1:X, fração 1/X e porcentagem, com o fator de diluição e as partes de soluto/diluente. Aceita as duas convenções de 1:X (X = partes totais, ou 1 parte de soluto + X de diluente); informando o volume final, calcula os volumes a misturar. Exemplo clássico: 1:5 = 1/5 = 20 %; para 100 mL, misturar 20 mL de concentrado + 80 mL de diluente.
- [Calculadora de inversa modular (Euclides estendido)](https://elysiatools.com/pt/tools/modular-inverse-calculator): Calcula a⁻¹ mod m pelo algoritmo de Euclides estendido: fornece os coeficientes de Bézout a·x + m·y = gcd(a, m), a tabela completa de coeficientes diretos (cada linha satisfaz r = a·s + m·t) e a verificação a × a⁻¹ ≡ 1 (mod m). Aceita números do tamanho do RSA (até 10⁵¹²) e avisa claramente quando gcd(a, m) ≠ 1 torna a inversa inexistente. Clássico: no RSA, 17⁻¹ mod 3120 = 2753.
- [Calculadora de aritmética modular (soma / subtração / produto / inversa / potência)](https://elysiatools.com/pt/tools/modulo-arithmetic-converter): Calcula soma, subtração, produto, inversa e potência rápida módulo m com aritmética BigInt exata (até 10¹⁸). As operações básicas mostram a redução passo a passo e devolvem o representante canônico em \[0, m−1\]; a inversa usa o algoritmo de Euclides estendido e avisa quando gcd(a, m) ≠ 1; a potência rápida exibe a tabela de elevar-ao-quadrado-e-multiplicar para os bits do expoente. Exemplos: 17⁵ mod 13 = 10; 5⁻¹ mod 18 = 11.
- [Gerador de tabelas-verdade](https://elysiatools.com/pt/tools/truth-table-generator): Gera a tabela-verdade completa de uma expressão booleana (até 6 variáveis, 64 linhas): suporta + OU, ^ XOR, ·/*/& ou justaposição E, !/~/' NÃO e parênteses; as variáveis são listadas alfabeticamente, cada linha mostra a atribuição e o valor F, e são dadas as formas canônicas Σm (minterms) e ΠM (maxterms). Clássicos: AB + A'C tem Σm(1,3,6,7); A ^ B ^ C é a função de paridade ímpar Σm(1,2,4,7).
- [Conversor de Velocidade Angular (rad/s / rpm / deg/s / Hz)](https://elysiatools.com/pt/tools/angular-velocity-converter): Conversão de velocidade angular: rad/s (base SI) ↔ rpm (1=2π/60 rad/s) ↔ grau/s (1=π/180 rad/s) ↔ Hz (1 rotação/s=2π rad/s). Hz aqui = rotação por segundo. Conversão via rad/s com os quatro equivalentes. Ref.: vinil 33⅓ rpm≈3,49 rad/s, marcha lenta ~800 rpm≈83,8 rad/s.
- [Calculadora de Dimensionamento de Duto (vazão e velocidade)](https://elysiatools.com/pt/tools/duct-size-calculator): Dimensiona um duto a partir da vazão Q e velocidade de projeto v: seção A=Q/v. Circular: diâmetro D=√(4A/π). Retangular com razão r=a/b: b=√(A/r), a=r·b, diâmetro equivalente ASHRAE D_eq=1,30·(a·b)^0,625/(a+b)^0,25. Vazão em m³/s/m³/h/CFM; resultados em mm e polegadas.
- [Calculadora de Limite de Fadiga (Goodman/Gerber/Soderberg)](https://elysiatools.com/pt/tools/fatigue-limit-calculator): Fator de segurança em fadiga com correção por tensão média. Dados σ_a, σ_m e σ_uts, σ_-1, σ_y: três critérios clássicos — Goodman modificado (linear, conservador), Gerber (parabólico, melhor para dúcteis) e Soderberg (via σ_y, o mais conservador). O menor é o valor governante; indica se o ponto está dentro da linha de Goodman.

## Exemplos

- [Exemplos de Processamento de Imagem Web Python](https://elysiatools.com/pt/samples/web-image-processing-python): Exemplos de processamento de imagem Web Python usando PIL/Pillow incluindo leitura, salvamento, redimensionamento e conversão de formato
- [Exemplos de Processamento de Imagem Android Java](https://elysiatools.com/pt/samples/android-image-processing-java): Exemplos de processamento de imagem Android Java incluindo leitura/escrita, dimensionamento e conversão de formato
- [Exemplos de Processamento de Imagem Android Kotlin](https://elysiatools.com/pt/samples/android-image-processing-kotlin): Exemplos de processamento de imagem Android Kotlin incluindo leitura/escrita, dimensionamento e conversão de formato
- [Exemplos de Processamento de Imagem Web Rust](https://elysiatools.com/pt/samples/web-image-processing-rust): Exemplos de processamento de imagem Web Rust incluindo leitura/gravação, redimensionamento e conversão de formato