Algoritmo de Euclides

desc

 

→ Confira uma calculadora de mmc ou de mdc entre dois números naturais (clique aqui)

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 R1. Se R1 for zero, o mdc entre X e Y é Y.
      2. Se R1 não for zero, divida Y por R1 e obtenha o resto R2. Se R2 for zero, o mdc entre X e Y é R1.
      3. Se R2 não for zero, divida R1 por R2 e obtenha o resto R3. Se R3 for zero, o mdc entre X e Y é R2.
      4. ...
      5. Se Rn não for zero, divida Rn-1 por Rn e obtenha o resto Rn+1. Se Rn+1 for zero, o mdc entre X e Y é Rn

Exemplo

Obter, pelo Algoritmo de Euclides, o mdc entre 10 e 15.

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

Obter, pelo Algoritmo de Euclides, o mdc entre 1128 e 336.

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)

 

Professor Cardy
Simulado Enem 2014

Simulado ENEM 2014

Teste seus conhecimentos com questões do ENEM

Aprenda mais sobre isso!

Simulado FUVEST

Simulado FUVEST 2014

Teste seus conhecimentos com questões da FUVEST

Aprenda mais sobre isso!

Simulado Pesadelo

Simulado Pesadelo

Teste seus conhecimentos com questões mais difíceis do site

Aprenda mais sobre isso!

Simulado Raciocínio Lógico

Simulado Raciocínio Lógico

Teste seus conhecimentos com questões de Raciocínio Lógico

Aprenda mais sobre isso!

Calculadora de Porcentagem

Calculadora de Porcentagem

Utilize o aplicativo para aprender porcentagem

Aprenda mais sobre isso!

Calculadora de Imposto de Renda

Calculadora de Imposto de Renda

Retido na Fonte mensal

Aprenda mais sobre isso!

Gerador de Provas

Desafios de Lógica

Desafios de Raciocínio Lógico

Aprenda mais sobre isso!

Gerador de Listas de Exercícios

Gerador de Listas de Exercícios

De todas as disciplinas do Ensino Médio

Aprenda mais sobre isso!




 

ProfCardy.Com

2001 — 2014

14 anos on line!
GRATUITAMENTE, com acesso TOTAL e completamente liberado!