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

 

Avalie esta página

Muito Supimpa Pesadelo

Supimpa
Pesadelo

Normal
Pesadelo

Mequetrefe
Pesadelo
Muito Mequetrefe
Pesadelo

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.