Algoritmo de Euclides: implementações e aplicações do MDC

Utilizado para o cálculo do máximo divisor comum (MDC) entre dois números inteiros, o algoritmo de Euclides é um dos algoritmos mais famosos e antigos da Matemática, sendo um ótimo exemplo para apresentar a recursividade para quem está aprendendo o assunto.

Como o título sugere, o objetivo desta postagem é apresentar a implementação do algoritmo (especificamente em Java, C e em Javascript) e algumas aplicações do MDC.

Caso o interesse do leitor seja o formalismo matemático por trás do algoritmo, sugiro que o mesmo consulte as referências no final da postagem.

O Algoritmo de Euclides

Sem delongas, o algoritmo de Euclides é [1][2]

$$\operatorname{mdc}(a,b)=\begin{cases}a,\quad\text{se}\, b=0\\ \operatorname{mdc}(b, a\,\%\,b),\quad\text{caso contrário}\end{cases}$$

onde $a>0$ e $b\geq 0$ e $a,b\in\mathbb{Z}$.

O primeiro caso é o caso base, isto é, se $b$ é zero, então o MDC será $a$. Isso faz sentido, pois zero é divisível por qualquer número inteiro (exceto zero).

O segundo caso é a solução recursiva: o MDC entre $a$ e $b$ é igual ao MDC entre $b$ e o resto da divisão de $a$ por $b$.

Em pseudocódigo teríamos:

1. mdc(a, b)
2. |   se(b = 0)
3. |   |   retorne a
4. |   senão
5. |   |   retorne mdc(b, a % b)
6. |   fim_se
7. fim_mdc

É possível também escrever o algoritmo iterativamente

1. mdc(a, b)
2. |   enquanto(b ≠ 0)
3. |   |   resto ← a % b
4. |   |   a ← b
5. |   |   b ← resto
6. |   fim_enquanto
7. |   retorne a
8. fim_mdc

Exemplos

Para demonstrar o funcionamento do algoritmo, vamos dar alguns exemplos:

$$\begin{align*}\operatorname{mdc}(30,60)&=\operatorname{mdc}(60, 30\,\%\,60)\\&=\operatorname{mdc}(60, 30)\\&=\operatorname{mdc}(30, 60\,\%\,30)\\&=\operatorname{mdc}(30, 0)\\&=30\end{align*}$$

Observação rápida: o resto da divisão de 30 por 60 é igual a 30 porque 30/60 = 0 (estamos lidando com divisões inteiras).

$$\begin{align*}\operatorname{mdc}(50,12)&=\operatorname{mdc}(12, 50\,\%\,12)\\&=\operatorname{mdc}(12, 2)\\&=\operatorname{mdc}(2, 12\,\%\,2)\\&=\operatorname{mdc}(2, 0)\\&=2\end{align*}$$

$$\begin{align*}\operatorname{mdc}(100,11)&=\operatorname{mdc}(11, 100\,\%\,11)\\&=\operatorname{mdc}(11, 1)\\&=\operatorname{mdc}(1, 11\,\%\,1)\\&=\operatorname{mdc}(1, 0)\\&=1\end{align*}$$

Quando o MDC entre dois números é igual a 1, dizemos que esses números são primos entre si.

Códigos

Os códigos a seguir implementam a versão recursiva e a versão iterativa do algoritmo de Euclides.

Algoritmo de Euclides em Java

//Código por Henrique Felipe (GitHub: HenriqueIni)
public class MDC {
    //Algoritmo de Euclides recursivo
    public static int mdcRecursive(int a, int b){
        if(b == 0) return a;
        return mdcRecursive(b, a % b);
    }
    //Algoritmo de Euclides iterativo
    public static int mdcIterative(int a, int b){
        while(b != 0){
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
    public static void main(String[] args) {
        //Teste da versão recursiva
        System.out.println("MDC recusive");
        System.out.printf("mdc(30, 60) = %d\n", mdcRecursive(30, 60));
        System.out.printf("mdc(50, 12) = %d\n", mdcRecursive(50, 12));
        System.out.printf("mdc(100, 11) = %d\n", mdcRecursive(100, 11));
        //Teste da versão iterativa
        System.out.println("\nMDC iterative");
        System.out.printf("mdc(30, 60) = %d\n", mdcIterative(30, 60));
        System.out.printf("mdc(50, 12) = %d\n", mdcIterative(50, 12));
        System.out.printf("mdc(100, 11) = %d", mdcIterative(100, 11));
    }
}

Algoritmo de Euclides em C

//Código por Henrique Felipe (GitHub: HenriqueIni)
#include <stdio.h>
#include <stdlib.h>

//Algoritmo de Euclides recursivo
int mdcRecursive(int a, int b){
    if(b == 0) return a;
    return mdcRecursive(b, a % b);
}
//Algoritmo de Euclides iterativo
int mdcIterative(int a, int b){
    while(b != 0){
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}
int main() {
    //Teste da versão recursiva
    printf("MDC recusive\n");
    printf("mdc(30, 60) = %d\n", mdcRecursive(30, 60));
    printf("mdc(50, 12) = %d\n", mdcRecursive(50, 12));
    printf("mdc(100, 11) = %d\n", mdcRecursive(100, 11));
    //Teste da versão iterativa
    printf("\nMDC iterative\n");
    printf("mdc(30, 60) = %d\n", mdcIterative(30, 60));
    printf("mdc(50, 12) = %d\n", mdcIterative(50, 12));
    printf("mdc(100, 11) = %d", mdcIterative(100, 11));
    return 0;
}

Algoritmo de Euclides em Javascript

//Código por Henrique Felipe (GitHub: HenriqueIni)

//Algoritmo de Euclides recursivo
function mdcRecursive(a, b) {
    if (b == 0) {
        return a;
    }
    return mdcRecursive(b, a % b);
}
//Algoritmo de Euclides iterativo
function mdcIterative(a, b) {
    while(b != 0){
        var r = a % b;
        a = b;
        b = r;
    }
    return a;
}
function tests() {
    //Teste da versão recursiva
    var output = "MDC recusive\n";
    output += "mdc(30, 60) = " + mdcRecursive(30, 60) + "\n";
    output += "mdc(50, 12) = " + mdcRecursive(50, 12) + "\n";
    output += "mdc(100, 11) = " + mdcRecursive(100, 11) + "\n\n";
    //Teste da versão iterativa
    output += "MDC iterative\n";
    output += "mdc(30, 60) = " + mdcIterative(30, 60) + "\n";
    output += "mdc(50, 12) = " + mdcIterative(50, 12) + "\n";
    output += "mdc(100, 11) = " + mdcIterative(100, 11);
    //saída
    alert(output);
}

Complexidade no Tempo

O algoritmo de Euclides tem complexidade no tempo de $O(\log b)$ [1].

Aplicações do MDC

Apesar do MDC ser uma operação bem simples, ela possui muitas aplicações importantes:

• no teste de primalidade AKS, há uma etapa em que é necessário verificar se dois número são primos entre si, algo que pode ser feito utilizando o MDC. Para quem não sabe, o teste de primalidade AKS é um algoritmo polinomial e determinístico capaz de verificar se um número é primo ou composto [4];
• no algoritmo de criptografia RSA, que é um dos mais conhecidos e utilizados, também há um passo no qual é necessário verificar se dois número são primos entre si [3];
• o MDC também é utilizado para simplificar frações;
• através do MDC, podemos calcular eficientemente o MMC (mínimo múltiplo comum) entre dois números, algo que normalmente envolve a fatoração de números inteiros (que não é computacionalmente eficiente).

Referências

[1] IME-USP (2004). Máximo divisor comum.

[2] KILHIAN, K. (2012). O Algoritmo de Euclides para Determinação do MDC.

[3] SOUSA, A. N. L. (2013). Criptografia de chave pública, criptografia RSA.

[4] AGRAWAL, M., KAYAL, N., & SAXENA, N. (2004). PRIMES is in P. Annals of mathematics, 781-793.