Use o método das divisões sucessivas para calcular o Máximo Divisor Comum e a Identidade de Bezout para os pares abaixo. Ainda, verifique o mdc encontrado através do Teorema Fundamental da Aritmética, ou seja, através de fatorações.
b) -20 e -84
b) -20 e -84
Passo 1
O enunciado pede três coisas para o par de inteiros
e
:
- Calcular o máximo divisor comum usando o método das divisões sucessivas (algoritmo de Euclides).
- Determinar uma identidade de Bézout, ou seja, encontrar inteiros
e tais que . - Verificar o
encontrado usando fatorações em números primos (Teorema Fundamental da Aritmética).
Informações dadas:
- Os dois inteiros são
e .
Passo 2
Rápida aula sobre o método que vamos usar (sem mistério):
- O algoritmo de Euclides usa divisões sucessivas para calcular o
. Se e são inteiros com , escrevemos
depois
e assim por diante até obter um resto zero. O último resto não nulo é o
.
- Para obter a identidade de Bézout (coeficientes que representam o
como combinação linear), voltamos substituindo os restos encontrados (retro-substituição). - Observação sobre sinais:
é sempre tomado não-negativo. Normalmente aplicamos o algoritmo às magnitudes (valores absolutos) e , e depois adaptamos a identidade para os sinais originais.
Passo 3
Aplicando as divisões sucessivas a
e
(usei os valores absolutos porque o algoritmo tradicional usa números positivos):
Primeira divisão:
Aqui
e
.
Segunda divisão:
Aqui o resto é
, portanto o algoritmo termina e o último resto não nulo é
.
Logo,
Como
(o
ignora sinais), concluímos
Passo 4
Agora vamos obter a identidade de Bézout por retro-substituição. Da primeira equação do algoritmo temos:
Isso já é uma combinação linear de
e
:
.
Mas o enunciado pediu a identidade em termos de
e
. Se escrevemos
e
, então
Portanto uma identidade de Bézout para os números originais é
Vamos checar rapidamente:
confere.
Passo 5
Comentário sobre soluções gerais (útil na prova): se
é uma solução da identidade
, então todas as soluções inteiras são dadas por
onde
. Como
e
, a família de soluções é
Exemplo: para
recupera-se
; para
obtemos
, que também satisfaz a identidade.
Passo 6
Verificação do
via fatoração em primos (Teorema Fundamental da Aritmética):
Fatoraçõess:
O MDC é o produto dos primos comuns com os menores expoentes. O único primo comum é
com expoente mínimo
. Portanto
o que confirma o resultado obtido pelo algoritmo de Euclides.
Resposta
Identidade de Bézout (uma solução):
Verificação por fatoração: