Calcule o máximo divisor comum (MDC) de 9652 e 252 utilizando o algoritmo de Euclides.
Passo 1
Beleza, o enunciado pede pra calcular o máximo divisor comum (MDC) de 9652 e 252 usando o algoritmo de Euclides. Isso faz parte de Matemática Discreta ou Aritmética: a ideia é usar divisões sucessivas com resto até o resto virar zero. Vamos precisar saber como dividir dois números inteiros e anotar o quociente e o resto em cada passo.
Passo 2
Teoria rapidinha: o algoritmo de Euclides usa a propriedade
seja e
inteiros com
. Se fizermos
seja
então
.
Repetimos isso, sempre trocando por
, até o resto
ser zero. Quando
, o MDC é o último divisor não-nulo.
Repetimos isso, sempre trocando
Passo 3
Primeira divisão: vamos dividir 9652 por 252.
Calculamos o quociente inteiro:
Calculamos o quociente inteiro:
logo o resto é
Então
e
.
Passo 4
Agora dividimos 252 por 76.
O quociente inteiro é 3, porque
O quociente inteiro é 3, porque
e o resto é
Então
logo
.
Passo 5
Seguinte, 76 dividido por 24 dá quociente 3 (já que
) e resto
Isso é
portanto
.
Passo 6
Finalmente, dividimos 24 por 4.
Ou seja,
Quando o resto vira zero, paramos: o MDC é o último divisor não-nulo, que aqui é 4.
Resposta
O máximo divisor comum de 9652 e 252 é 4.