[Revisão] Use o algoritmo de Euclides para calcular o \operatorname{mdc}(a, b) nos pares abaixo, escrevendo todas as divisões sucessivas:
\operatorname{mdc}(126,45)

Passo 1

O enunciado pede para calcular o \operatorname{mdc}(126,45) usando o algoritmo de Euclides e escrevendo todas as divisões sucessivas.
Informações dadas: \,126 e \,45. Não preciso de mais nada além desses dois números.

Passo 2

O que é o algoritmo de Euclides (explicação didática)?
Pelo teorema da divisão inteira, para dois inteiros positivos a e b existe um quociente q e um resto r tais que
a = b\cdot q + r,
com 0 \le r < b. No algoritmo de Euclides usamos essa divisão repetidamente. Uma propriedade-chave: \gcd(a,b)=\gcd(b,r). Ou seja, o máximo divisor comum de a e b é o mesmo que o de b e do resto r. Repetimos até obter resto 0; então o último resto não nulo é o \gcd.
Explicando as variáveis: em cada passo a é o dividendo (número maior), b é o divisor (número menor), q é o quociente inteiro, e r é o resto (o que sobra). Vou aplicar isso passo a passo para (126,45).

Passo 3

Primeira divisão: dividir 126 por 45. Escolhemos o maior q inteiro tal que 45\cdot q \le 126.
Verificações: 45\cdot 2 = 90 \le 126 e 45\cdot 3 = 135 > 126. Portanto q=2. O resto r é 126 - 45\cdot 2 = 126 - 90 = 36. Escrevendo na forma da divisão:
126 = 45\cdot 2 + 36.
Cheque: 0 \le 36 < 45, está correto.

Passo 4

Segundo passo do algoritmo: agora aplicamos a divisão usando o divisor anterior 45 e o resto 36. Dividimos 45 por 36. Escolhemos o maior q inteiro tal que 36\cdot q \le 45.
Verificações: 36\cdot 1 = 36 \le 45 e 36\cdot 2 = 72 > 45. Então q=1. O resto é 45 - 36\cdot 1 = 9. Escrevendo:
45 = 36\cdot 1 + 9.
Cheque: 0 \le 9 < 36, correto.

Passo 5

Terceiro passo: dividimos 36 (dividendo) por 9 (divisor). Buscamos q tal que 9\cdot q \le 36.
Verificações: 9\cdot 4 = 36 \le 36 e 9\cdot 5 = 45 > 36. Portanto q=4. O resto é 36 - 9\cdot 4 = 0. Escrevendo:
36 = 9\cdot 4 + 0.
Quando o resto é 0, o algoritmo termina: o último resto não nulo (aqui 9) é o \gcd.

Passo 6

Interpretação final e checagem: pelo algoritmo, \gcd(126,45) é o último resto não nulo, que é 9. Verificação rápida: 9 divide 126 porque 126 = 9\cdot 14 e divide 45 porque 45 = 9\cdot 5. E por construção do algoritmo nenhum divisor comum maior que 9 pode existir. Portanto o resultado está correto.

Resposta

\operatorname{mdc}(126,45)=9

Exercícios relacionados