[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 e escrevendo todas as divisões sucessivas.
Informações dadas: e
. Não preciso de mais nada além desses dois números.
Informações dadas:
Passo 2
O que é o algoritmo de Euclides (explicação didática)?
Pelo teorema da divisão inteira, para dois inteiros positivos e
existe um quociente
e um resto
tais que
Pelo teorema da divisão inteira, para dois inteiros positivos
com
. No algoritmo de Euclides usamos essa divisão repetidamente. Uma propriedade-chave:
. Ou seja, o máximo divisor comum de
e
é o mesmo que o de
e do resto
. Repetimos até obter resto
; então o último resto não nulo é o
.
Explicando as variáveis: em cada passo
é o dividendo (número maior),
é o divisor (número menor),
é o quociente inteiro, e
é o resto (o que sobra). Vou aplicar isso passo a passo para
.
Passo 3
Primeira divisão: dividir
por
. Escolhemos o maior
inteiro tal que
.
Verificações: e
. Portanto
. O resto
é
. Escrevendo na forma da divisão:
Verificações:
Cheque:
, está correto.
Passo 4
Segundo passo do algoritmo: agora aplicamos a divisão usando o divisor anterior
e o resto
. Dividimos
por
. Escolhemos o maior
inteiro tal que
.
Verificações: e
. Então
. O resto é
. Escrevendo:
Verificações:
Cheque:
, correto.
Passo 5
Terceiro passo: dividimos
(dividendo) por
(divisor). Buscamos
tal que
.
Verificações: e
. Portanto
. O resto é
. Escrevendo:
Verificações:
Quando o resto é
, o algoritmo termina: o último resto não nulo (aqui
) é o
.
Passo 6
Interpretação final e checagem: pelo algoritmo,
é o último resto não nulo, que é
. Verificação rápida:
divide
porque
e divide
porque
. E por construção do algoritmo nenhum divisor comum maior que
pode existir. Portanto o resultado está correto.