Algoritmo de Euclides para calcular o maior divisor comum (MDC)

Dado dois inteiros não negativos $a$ e $b$, temos que encontrar seu Máximo Divisor Comum (MDC / GCD), ou seja, o maior número que é um divisor de $a$ e $b$. É geralmente indicado por $\gcd(a, b)$. Matematicamente, é definido como: $$\gcd(a, b) = \max_ {k = 1 \dots \infty ~ : ~ k \mid a ~ \wedge k ~ \mid b} k.$$ (aqui o símbolo "$\mid$" indica divisibilidade, ou seja, "$k \mid a$" significa "$k$ divide $a$")

Quando um dos números é zero, enquanto o outro é diferente de zero, seu maior divisor comum, por definição, é o segundo número. Quando ambos os números são zero, seu maior divisor comum é indefinido (pode ser qualquer número arbitrariamente grande), mas podemos defini-lo como zero. O que nos dá uma regra simples: se um dos números é zero, o maior divisor comum é o outro número.

O algoritmo de Euclides, discutido abaixo, permite encontrar o maior divisor comum de dois números $a$ e $b$ em $O(\log \min(a, b))$.

O algoritmo foi descrito pela primeira vez nos "Elementos" de Euclides (cerca de 300 A.C), mas é possível que o algoritmo tenha origens ainda anteriores.

Algoritmo

O algoritmo é extremamente simples:

$$\ mdc(a, b) = \begin{cases}a,&\text{ se }b = 0 \\ \ mdc(b, a \bmod b),&\text{caso contrario}\end{cases}$$

Implementação

Nota: GCD = MDC, MMC = LCM e % = mod.

int gcd (int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd (b, a % b);
}

Usando o operador em C++, podemos escrevê-lo como:

int gcd (int a, int b) {
    return b ? gcd (b, a % b) : a;
}

E, finalmente, aqui está uma implementação não recursiva:

int gcd (int a, int b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

Prova de Correção

Primeiro, observe que em cada iteração do algoritmo euclidiano o segundo argumento diminui estritamente; portanto (como os argumentos sempre são não negativos), o algoritmo sempre termina.

Para a prova da correção, precisamos mostrar que $\ mdc(a, b) = \ mdc(b, a \bmod b)$ para todo $a \geq 0$, $b > 0$.

Mostraremos que o valor no lado esquerdo da equação divide o valor no lado direito e vice-versa. Obviamente, isso significaria que os lados esquerdo e direito são iguais, o que provará o algoritmo de Euclides.

Seja $d = \ mdc(a, b)$. Então, por definição $d\mid a$ e $d\mid b$.

Agora vamos representar o restante da divisão de $a$ por $b$ da seguinte maneira: $$a \bmod b = a - b \cdot \Bigl\lfloor\dfrac{a}{b}\Bigr\rfloor$$

Daí resulta que $d \mid (a \bmod b)$, o que significa que temos o sistema de divisibilidades: $$\begin{cases}d \mid b,\\ d \mid (a \mod b)\end{cases}$$

Agora usamos o fato de que, para quaisquer três números $p$, $q$, $r$, se $p\mid q$ e $p\mid r$ então $p\mid \ mdc(q, r)$. No nosso caso: $$d = \ mdc(a, b) \mid \ mdc(b, a \mod b)$$

Assim, mostramos que o lado esquerdo da equação original divide o direito. A segunda metade da prova é semelhante.

Complexidade de Tempo

O tempo de execução do algoritmo é estimado pelo teorema de Lamé, que estabelece uma conexão surpreendente entre o algoritmo euclidiano e a sequência de Fibonacci:

Se $a > b \geq 1$ e $b < F_n$ para algum $n$, o algoritmo de Euclides executa no máximo $n-2$ chamadas recursivas.

Além disso, é possível mostrar que o limite desse teorema é otimizado. Quando $a = F_n$ e $b = F_{n-1}$, $mdc(a, b)$ will executará exatamente $n-2$ chamadas. Em outras palavras, os números consecutivos de Fibonacci são o pior caso de input para o algoritmo de Euclides.

Dado que os números de Fibonacci crescem exponencialmente, concluímos que o algoritmo funciona em $O(\log \min(a, b))$.

Mínimo Múltiplo Comum

O cálculo do mínimo múltiplo comum (denotado como MMC / LCM) pode ser reduzido calculando o MDC / GCD com a seguinte fórmula: $$\text{lcm}(a, b) = \frac{a \cdot b}{\ gcd(a, b)}$$

Assim, MMC / LCM pode ser calculado usando o algoritmo de Euclides com a mesma complexidade de tempo:

Uma possível implementação, que habilmente evita o overflow de números inteiros dividindo primeiro $a$ com o GCD / MDC, é apresentada aqui:

int lcm (int a, int b) {
    return a / gcd(a, b) * b;
}

Problemas