Já tratei da decomposição de um número natural em fatores primos. Isso certamente é suficiente para obter o mdc entre dois ou vários números naturais. No entanto, para obter o mdc entre dois números naturais muito grandes isso fica complicado porque a decomposição pode não ser imediata.
O método a seguir é baseado no livro sétimo dos Elementos de Euclides. Apesar de existirem evidências históricas que este método seja anterior a este livro... O Algoritmo de Euclides para a obtenção do máximo divisor comum entre dois números naturais é um processo bem simples. Não desista ao ler a explicação pelo roteiro, mas acompanhe o roteiro juntamente com os exemplos numéricos que virão a seguir - vai ficar bem mais fácil.
Roteiro
Obtendo o mdc entre dois números naturais $$X$$ e $$Y$$ onde $$X > Y$$.
1) Divida $$X$$ por $$Y$$ e obtenha o resto $$R_1$$. Se $$R_1$$ for zero, o mdc entre $$X$$ e $$Y$$ é $$Y$$.
2) Se $$R_1$$ não for zero, divida $$Y$$ por $$R_1$$ e obtenha o resto $$R_2$$. Se $$R_2$$ for zero, o mdc entre $$X$$ e $$Y$$ é $$R_1$$.
3) $$R_2$$ não for zero, divida $$R_1$$ por $$R_2$$ e obtenha o resto $$R_3$$. Se $$R_3$$ for zero, o mdc entre $$X$$ e $$Y$$ é $$R_2$$.
...
Se $$R_n$$ ão for zero, divida $$R_{n-1}$$ por $$R_n$$ e obtenha o resto $$R_{n+1}$$. Se $$R_{n+1}$$ for zero, o mdc entre $$X$$ e $$Y$$ é $$R_n$$
Exemplo 1
Obter, pelo Algoritmo de Euclides, o mdc entre 10 e 15.
Resolução
Dividimos 15 por 10 (porque 15 é maior que 10).
| dividendo | divisor |
| 15 | 10 |
| 5 | 1 |
| resto | quociente |
Como o resto é 5 (não vale zero), devemos dividir o divisor 10 por 5, temos:
| dividendo | divisor |
| 10 | 5 |
| 0 | 2 |
| resto | quociente |
O resto é zero, portanto o mdc entre 15 e 10 é 5 (o divisor da divisão cujo resto é zero).
→ Confira com uma calculadora de mmc ou de mdc entre dois números naturais clique aqui
O Algoritmo de Euclides pode requistar muitas divisões sucessivas até que se chegue ao resto zero (sempre se chegará). Por conta disso, é melhor usar uma chave que aproveita melhor os resultados anteriores e deixa espaço para os próximos, caso sejam necessários.
Monte uma grade com, pelo menos, 3 colunas e exatamente 3 linhas (deixe espaço à direita):
Na grade, insira o 15 e o 10 (vou manter os números do exemplo) assim:
| 15 | 10 | ||
Sempre na primeira linha, sobre o último divisor usado, escreva o quociente da divisão atual. Na divisão de 15 por 10 o quociente é 1. Registre assim:
| 1 | |||
| 15 | 10 | ||
O resto da divisão atual é registrado abaixo do dividendo da divisão atual. Na divisão de 15 por 10 o resto é 5.
| 1 | |||
| 15 | 10 | ||
| 5 |
Como 5 não é zero, compiamos o 5 ao lado do 10, na próxima casa. Repete-se todo o processo anterior, pensando que a divisão de agora é de 10 por 5.
| 1 | |||
| 15 | 10 | 5 | |
| 5 |
Na divisão de 10 por 5 o quociente é 2. Registre assim:
| 1 | 2 | ||
| 15 | 10 | 5 | |
| 5 |
Na divisão de 10 por 5 o resto é 0.
| 1 | 2 | ||
| 15 | 10 | 5 | |
| 5 | 0 |
Como o resto é zero, o mdc entre 15 e 10 é o número 5.
Exemplo 2
Obter, pelo Algoritmo de Euclides, o mdc entre 1128 e 336.
Resolução
Após as divisões sucessivas e os registros dos resultados nos locais apropriados, chega-se em:
| 3 | 2 | 1 | 4 | |
| 1128 | 336 | 120 | 96 | 24 |
| 120 | 96 | 24 | 0 |
O mdc entre 1128 e 336 é 24.
→ Confira com uma calculadora de mmc ou de mdc entre dois números naturais clique aqui