Calcule
e
.
Passo 1
O problema pede para calcular os dois máximos divisores comuns abaixo:
e
.
Informações dadas: os pares de inteiros são e
. Não há outras restrições.
Informações dadas: os pares de inteiros são
Passo 2
O que é
? A definição:
é o maior inteiro positivo que divide simultaneamente
e
. Duas propriedades importantes que vamos usar:
ou seja, sinais não importam — podemos trabalhar com valores absolutos; e o algoritmo de Euclides é uma maneira eficiente de calcular
. O algoritmo de Euclides usa divisões sucessivas: se
com
, então
Repetimos até o resto ser
; o último resto não nulo é o
.
Passo 3
Vamos aplicar o algoritmo de Euclides em
. Primeiro, por segurança, usamos valores absolutos (mas já são positivos):
.
Fazemos a divisão de por
:
Fazemos a divisão de
porque
e
. Pelo algoritmo,
Passo 4
Continuamos dividindo
por
:
pois
e
. Assim
Passo 5
Dividimos
por
:
pois
e
. Logo
Passo 6
Dividimos
por
:
pois
e
. Então
Passo 7
Dividimos
por
:
O resto é
, então o último resto não nulo é
. Portanto
Interpretação:
e
são primos entre si (não têm divisores comuns maiores que
).
Passo 8
Como verificação alternativa, olhe a fatoração em primos rápida:
e, observando que
, não há fator
em
, então não há fatores comuns e o
é
. Isso confirma o resultado do algoritmo de Euclides.
Passo 9
Agora calculamos
. Pela propriedade dos valores absolutos,
Passo 10
Aplicando o algoritmo de Euclides em
: divida
por
:
O resto é
, então o último resto não nulo é
. Portanto
Passo 11
Verificação por fatoração:
e
. O produto dos fatores comuns com o menor expoente é
, confirmando o resultado.