Esse blog é de caráter pessoal e destina-se aos alunos e companheiros interessados em Matemática.
Sendo a internet uma vasta rede de informações que se perde em quantidade de conteúdo, o que pretendemos é juntar todas essas informações em um local que meus alunos possam ter acesso de forma mais simples. Logo para construção desse blog o que estamos fazendo é garimpando na rede tudo que consideramos relevante e postando em um único lugar.

terça-feira, 13 de dezembro de 2011

TEORIA DOS NÚMEROS - ALGORITMO DE EUCLIDES


ALGORITIMO DE EUCLIDES PARA OBTENÇÃO DO MÁXIMO DIVISOR COMUM (MDC)

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




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 12 e 15.

Vamos usar a grade prática. A primeira etapa fica assim:

1


15
12


3



A segunda etapa fica assim:

1
4

15
12
3

3
0


O mdc entre 12 e 15 é 3.


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.