Calculadora do Algoritmo Euclidiano Estendido

A Calculadora do Algoritmo Euclidiano Estendido calcula o Máximo Divisor Comum (MDC) de dois números inteiros e encontra os coeficientes de Bézout — os inteiros s e t que satisfazem mdc(a, b) = s·a + t·b. Além de calcular o MDC, esta ferramenta fornece uma tabela de divisão passo a passo totalmente animada, substituição reversa e cálculo de inverso modular, tornando-a ideal para cursos de teoria dos números, estudo de criptografia e programação competitiva.

O que é o Algoritmo de Euclides Estendido?

O Algoritmo de Euclides Estendido (AEE) é uma extensão do algoritmo clássico de MDC de Euclides. Enquanto o algoritmo básico encontra o mdc(a, b) por divisões sucessivas, a versão estendida rastreia simultaneamente duas sequências de inteiros que registram como cada resto pode ser expresso como uma combinação linear das entradas originais.

Como Funciona o Algoritmo

O AEE mantém três pares de valores — (r, s, t) — através de cada etapa de divisão:

1. Inicializar: r₀ = |a|, r₁ = |b|, s₀ = 1, s₁ = 0, t₀ = 0, t₁ = 1
2. Cada etapa: calcular o quociente q = ⌊rₙ₋₁ / rₙ⌋, então atualizar rₙ₊₁ = rₙ₋₁ − q·rₙ, sₙ₊₁ = sₙ₋₁ − q·sₙ, tₙ₊₁ = tₙ₋₁ − q·tₙ
3. Parar quando o resto = 0; o resto anterior é o mdc(a, b)
4. Os valores s e t correspondentes são os coeficientes de Bézout

Exemplo Passo a Passo: mdc(252, 105)

Resultado: mdc(252, 105) = 21, com identidade de Bézout: 21 = (−2) × 252 + 5 × 105 (s = −2, t = 5). Tente você mesmo com a calculadora acima para obter coeficientes exatos.

Aplicações do Algoritmo de Euclides Estendido

1. Inverso Modular (Criptografia)

A aplicação mais importante é o cálculo de inversos modulares. Se mdc(a, m) = 1, então o coeficiente de Bézout s satisfaz:

Os inversos modulares são essenciais na criptografia RSA (cálculo do expoente da chave privada d), troca de chaves Diffie-Hellman e criptografia de curva elíptica.

2. Resolvendo Equações Diofantinas Lineares

A equação ax + by = c tem soluções inteiras se e somente se mdc(a, b) divide c. Se sim, uma solução particular é x₀ = s·(c/d), y₀ = t·(c/d) onde d = mdc(a, b) e s, t são os coeficientes de Bézout.

3. Teorema Chinês do Resto

O AEE é usado na prova construtiva e no cálculo do Teorema Chinês do Resto — encontrando x tal que x ≡ a₁ (mod m₁) e x ≡ a₂ (mod m₂) — através do cálculo de inversos modulares dos módulos.

4. Redução de Frações e MMC

mdc(a, b) = 1 confirma que a/b já está em sua forma simplificada. O MMC é mmc(a, b) = |a·b| / mdc(a, b).

Os Coeficientes de Bézout Não São Únicos

Os coeficientes de Bézout s e t não são únicos. Se (s, t) for uma solução, então (s + k·(b/d), t − k·(a/d)) também será uma solução para qualquer inteiro k, onde d = mdc(a, b). O AEE retorna a solução onde |s| ≤ |b/d| e |t| ≤ |a/d|.

Complexidade de Tempo

O Algoritmo de Euclides Estendido é executado em O(log min(a, b)) iterações — o mesmo que o algoritmo básico de Euclides. Pelo teorema de Lamé, o número de etapas nunca excede 5 vezes o número de dígitos decimais da menor entrada. Isso o torna extremamente eficiente, mesmo para grandes números inteiros usados em aplicações criptográficas.

Perguntas Frequentes

O que é o Algoritmo de Euclides Estendido?

O Algoritmo de Euclides Estendido amplia o algoritmo de MDC de Euclides para também calcular os coeficientes de Bézout s e t que satisfazem mdc(a, b) = s·a + t·b. Ele acompanha como cada resto pode ser expresso como uma combinação linear de a e b durante o processo de divisão.

O que são coeficientes de Bézout?

Os coeficientes de Bézout são números inteiros s e t cuja existência é garantida pela identidade de Bézout (um teorema na teoria dos números). Eles satisfazem mdc(a, b) = s·a + t·b e são calculados eficientemente pelo Algoritmo de Euclides Estendido. Eles são usados no cálculo de inverso modular, na resolução de equações diofantinas e no Teorema Chinês do Resto.

Como encontrar o inverso modular usando o Algoritmo de Euclides Estendido?

Se mdc(a, b) = 1 (a e b são coprimos), o coeficiente de Bézout s satisfaz s·a ≡ 1 (mod b). O inverso modular de a mod b é s mod b (ajustado para ser positivo). Esta calculadora exibe isso diretamente nos resultados.

Quando o inverso modular não existe?

O inverso modular de a módulo m existe se e somente se mdc(a, m) = 1. Se mdc(a, m) > 1, nenhum número inteiro x satisfaz a·x ≡ 1 (mod m).

Qual é a complexidade de tempo do Algoritmo de Euclides Estendido?

O(log min(a, b)) divisões, igual ao algoritmo básico de Euclides. Pelo teorema de Lamé, o número de etapas é limitado a 5 vezes o número de dígitos decimais da menor entrada, o que o torna muito eficiente.