Voltar para .Sala de Estudo: Algoritmo de Euclides para determinação de MDC

Algoritmo de Euclides para determinação de MDC – Utilizando Diagramas

Vamos apresentar um modo mais simples de indicar as divisões sucessivas do Algoritmo de Euclides.
Observe…

Utilizando Diagramas




Podemos indicar as sucessivas divisões do Algoritmo de Euclides de uma maneira mais prática.
Vamos exemplificar como isso pode ser feito, utilizando as divisões obtidas no segundo exemplo.

1320 35      35 25      25 10      10 5
25 37      10 1      5 2      0 2

Essas divisões podem ser indicadas, utilizando-se um diagrama semelhante a um “Jogo da Velha ampliado”.
Veja:

37 1 2 2
1320 35 25 10 5
25 10 5 0

Observe que:

  • na primeira linha do diagrama, aparecem os quocientes das divisões efetuadas;
  • na segunda linha do diagrama, aparecem os divisores e dividendos das divisões efetuadas;
  • na terceira linha do diagrama, aparecem os restos das divisões efetuadas.

Pelo diagrama fica fácil de perceber que o MDC dos dois números em questão é o último resto não nulo do processo das divisões sucessivas.

Vejamos mais um exemplo; calculemos o mdc(23732,180):

1) Divisões

23732 180      180 152      152 28      28 12      12 4
152 131      28 1      12 5      4 2      0 3

2) Diagrama

  131 1 5 2 3
23732 180 152 28 12 4
152 28 12 4 0  

 
3) Conclusão
 
Como o último resto não nulo foi 4, então mdc(23732,180)=4.




Resumindo:




O algoritmo é simples, mas, mesmo usando o diagrama, pode dar muito trabalho, não é?

Probleminha2

Sim, dependendo dos números utilizados, dá trabalho. Mas, dentre as maneiras conhecidas de se calcular MDC, esse algoritmo é o menos trabalhoso. Para ajudar, vou deixar na próxima sala uma maquineta para calcular o MDC de pares de números naturais não nulos, pelo processo das divisões sucessivas.



Sonia Regina Di Giacomo
Equipe COM – OBMEP

Voltar para a Sala de Estudos sobre o Algoritmo de Euclides
Ir para a próxima sala

Link permanente para este artigo: http://clubes.obmep.org.br/blog/sala-de-estudos-algoritmo-de-euclides-para-determinacao-de-mdc/diagramas/

Deixe uma resposta