MDC com Coeficientes de Bézout

Identidade de Bézout e algoritmo de Euclides estendido

A identidade de Bézout afirma que para quaisquer inteiros a, b existem inteiros x, y tais que a · x + b · y = mdc(a, b). O algoritmo de Euclides estendido calcula o MDC junto com esses coeficientes: parte da recursão padrão mdc(a, b) = mdc(b, a mod b) e faz substituição reversa nos restos para recuperar x e y. Exemplo: mdc(15, 12) = 3 com 15 · 1 + 12 · (−1) = 3. Os coeficientes não são únicos — somar k · (b/mdc) a x e subtrair k · (a/mdc) de y dá outro par válido. O algoritmo continua sendo O(log min(a, b)).

Aplicações criptográficas e algorítmicas

• Inverso modular — essencial para o RSA: d ≡ e^(−1) (mod φ(n)) é exatamente o coeficiente de Bézout de e.
• Equações diofantinas lineares ax + by = c têm solução se e somente se mdc(a, b) | c; o algoritmo estendido produz uma solução particular.
• Teorema Chinês dos Restos — a prova construtiva combina congruências com módulos coprimos via coeficientes de Bézout.
• Algoritmos em redes e grafos — caminhos mínimos com pesos negativos (Bellman–Ford) e detecção de ciclos usam raciocínios próximos baseados em MDC.

Perguntas frequentes

Os coeficientes de Bézout são únicos? Não. Dado um par (x, y), todo (x + k · b/g, y − k · a/g) com k inteiro e g = mdc(a, b) também é válido.

Os coeficientes podem ser negativos? Sim — pelo menos um entre x e y costuma ser negativo quando ambos a, b > 0.

Quando o inverso modular a^(−1) mod n existe? Apenas quando mdc(a, n) = 1. O algoritmo estendido então devolve coeficientes com a · x + n · y = 1, e x mod n é o inverso.

Existe versão binária? Sim — o MDC estendido binário evita divisões e usa só shifts e subtrações, útil em hardware e implementações criptográficas em tempo constante.