Encontrar, usando o algoritmo de Euclides, o máximo divisor comum dos seguintes pares de números:
542 e 234
542 e 234
Passo 1
Então, o enunciado quer que a gente ache o maior divisor comum (MDC, ou gcd em inglês) de 542 e 234 usando o algoritmo de Euclides. Isso é parte de teoria dos números e a ideia básica é dividir repetidas vezes e ir pegando o resto até ele ser zero. Para isso, vamos precisar saber fazer divisões inteiras e interpretar quociente e resto.
Passo 2
Começamos dividindo 542 por 234.
Na prática:
Aqui o quociente é 2 e o resto é 74. Segundo o algoritmo de Euclides, agora trocamos: o próximo “a” será 234 e o “b” será 74.
Na prática:
Aqui o quociente é 2 e o resto é 74. Segundo o algoritmo de Euclides, agora trocamos: o próximo “a” será 234 e o “b” será 74.
Passo 3
Agora dividimos 234 por 74:
Quociente 3, resto 12. Troca de novo: a = 74, b = 12.
Quociente 3, resto 12. Troca de novo: a = 74, b = 12.
Passo 4
Dividimos 74 por 12:
Quociente 6, resto 2. Atualiza para a = 12, b = 2.
Quociente 6, resto 2. Atualiza para a = 12, b = 2.
Passo 5
Agora dividimos 12 por 2:
O resto deu 0, então a gente para por aqui.
O resto deu 0, então a gente para por aqui.
Resposta
Como chegamos a resto zero, o último divisor não nulo (que é 2) é o máximo divisor comum.
MDC(542, 234) = 2.