[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 é o algoritmo de Euclides (explicação curta e didática)?
- Para dois inteiros positivos
e com , dividimos por e obtemos um quociente e um resto: com . - Teorema chave:
. Ou seja, o máximo divisor comum não muda se substituirmos o maior número pelo resto da divisão. Repetimos o processo até o resto ser zero; então o último resto não nulo é o .
Vou aplicar isso passo a passo em todas as divisões sucessivas.
Passo 3
Primeira divisão (dividimos o maior pelo menor):
Verificação:
e
. O resto é
.
Passo 4
Segunda divisão (agora dividimos
por
):
Verificação:
e
. O resto é
.
Passo 5
Terceira divisão (dividimos
por
):
Verificação:
e
. O resto é
.
Passo 6
Quarta divisão (dividimos
por
):
Verificação:
e
. O resto é
.
Passo 7
Quinta divisão (dividimos
por
):
Verificação:
e
. O resto é
.
Passo 8
Sexta divisão (dividimos
por
):
Verificação:
e
. O resto é
.
Passo 9
Sétima divisão (dividimos
por
):
Verificação:
e
. O resto é
.
Passo 10
Oitava divisão (dividimos
por
):
Verificação:
e
. O resto é
.
Passo 11
Nona divisão (dividimos
por
):
O resto agora é
. Pelo algoritmo de Euclides, quando o resto é zero, o
é o último resto não nulo, que aqui é
.
Passo 12
Interpretação final e comentário rápido: como o último resto não nulo é
, os números
e
são primos entre si (ou seja, são coprimos). Bom trabalho por chegar até aqui — isso é exatamente o que a prova costuma pedir: listar as divisões até o resto zero.