[Revisão] Use o algoritmo de Euclides para calcular o
nos pares abaixo, escrevendo todas as divisões sucessivas:
Passo 1
O enunciado pede para calcular o
usando o algoritmo de Euclides, escrevendo todas as divisões sucessivas.
Dados fornecidos: e
.
Dados fornecidos:
Passo 2
O que vamos fazer (explicação didática do método que será usado): faremos divisões sucessivas do tipo
onde
e
são inteiros com
,
é o quociente inteiro e
é o resto com
. Em cada etapa substituímos o par
por
e repetimos. A sequência de restos é estritamente decrescente e termina quando o resto for zero; o último resto não nulo é o
. Intuitivamente: qualquer divisor comum de
e
divide também
; e qualquer divisor comum de
e
divide
. Por isso o conjunto de divisores comuns é preservado e o algoritmo encontra o maior deles.
Passo 3
Primeira divisão: dividimos
por
. Calculamos o quociente inteiro e o resto:
Verificação das contas:
e
. O resto
satisfaz
.
Passo 4
Segunda divisão: agora dividimos
pelo resto anterior
:
Verificação:
e
. O resto
satisfaz
.
Passo 5
Terceira divisão: dividimos
pelo novo resto
:
Aqui o resto é
, então o algoritmo termina.
Passo 6
Conclusão do algoritmo: como o último resto não nulo foi
, temos
Explicação curta do porquê: qualquer divisor comum de
e
divide os restos sucessivos
e
; e qualquer divisor comum de
e
divide
. Assim o maior divisor comum é o último resto não nulo.
Passo 7
Verificação extra por fatoração (para ficar mais seguro): fatorando,
Os fatores primos comuns são
e
; multiplicando
obtemos
, confirmando o resultado. Também dá para verificar que
e
, e
e
não têm divisores comuns além de
.