MDC (Algoritmo de Euclides)

Algoritmo de Euclides para o MDC

O algoritmo de Euclides chega ao mdc(a, b) aplicando a identidade mdc(a, b) = mdc(b, a mod b) vez após vez até que b = 0. O valor de a que sobra nesse ponto é o MDC. Ele aparece nos Elementos de Euclides (~300 a.C.), Livro VII, o que faz dele um dos algoritmos não-triviais mais antigos que ainda estão em uso. A complexidade é O(log min(a, b)), e o teorema de Lamé mostra que o pior caso surge quando as entradas são números de Fibonacci consecutivos.

Veja uma execução: mdc(48, 18) → mdc(18, 12) → mdc(12, 6) → mdc(6, 0) = 6. Há ainda o algoritmo estendido de Euclides, que entrega de quebra os coeficientes de Bézout x, y com a·x + b·y = mdc(a, b). É daí que sai o cálculo de inversos modulares.

Aplicações

• Criptografia: o inverso modular por trás da geração de chaves RSA e do ECDSA vem do Euclides estendido.
• Simplificação de frações: divida os dois termos de a/b por mdc(a, b) e você cai na forma irredutível.
• Equações diofantinas: ax + by = c só tem solução inteira quando mdc(a, b) divide c.
• Programação competitiva: é a escolha de sempre em problemas de teoria dos números.

Perguntas frequentes

Quanto vale mdc(a, 0)? Por convenção, mdc(a, 0) = |a|, e é justamente esse o caso-base da recursão.

Funciona com números negativos? Sim. Em geral as implementações tomam o módulo dos valores antes, já que o MDC é definido como não-negativo.

E para mais de dois números? Aproveite a associatividade e encadeie: mdc(a, b, c) = mdc(mdc(a, b), c).