 |
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: https://clubes.obmep.org.br/blog/sala-de-estudos-algoritmo-de-euclides-para-determinacao-de-mdc/diagramas/