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`

1

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.

 

2

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

 






Comente

São mais de 50.000 páginas de conteúdo . Não acompanho os diálogos a seguir - por isso, caso você ache alguma pergunta feita pelos usuários e queira contribuir, por favor, deixe o seu parecer - que irá enriquecer o material.