Vamos apresentar um modo mais simples de indicar as divisões sucessivas do Algoritmo de Euclides. |
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 é? |
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/