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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

//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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

//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

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

//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.