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.
d) 66 e 78
d) 66 e 78
Passo 1
O enunciado pede três coisas para o par de números
e
:
- Calcular o máximo divisor comum entre
e 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 valor do máximo divisor comum através da fatoração prima (Teorema Fundamental da Aritmética).
Dados fornecidos: os dois inteiros são
e
.
Passo 2
Vou explicar rapidamente o que é o método das divisões sucessivas (sem resolver ainda): dado dois inteiros positivos
e
com
, a divisão euclidiana diz que existem inteiros únicos
(quociente) e
(resto) tais que
O algoritmo de Euclides aplica essa divisão repetidamente, substituindo
por
até obter resto zero. O último resto não nulo é o
. Também, guardando as expressões das divisões, é possível voltar (substituir) para escrever o
como combinação linear de
e
— isso dá a identidade de Bézout.
Passo 3
Aplicando o algoritmo de Euclides às entradas
e
. Começo dividindo o maior pelo menor:
Aqui o quociente é
e o resto é
(pois
). Agora continuo dividindo
pelo último resto
:
Quociente
, resto
. Repito dividindo
por
:
O resto agora é
, então o algoritmo termina. O último resto não nulo é
. Portanto:
Passo 4
Agora vou mostrar detalhadamente como extrair a identidade de Bézout a partir das divisões que fizemos (método de substituição reversa). Reescrevo as igualdades relevantes com foco nos restos:
Da primeira divisão:
Da segunda divisão:
Queremos escrever
como combinação linear de
e
. Substituímos
da primeira equação na segunda.
Passo 5
Substituição passo a passo:
Da primeira equação temos
Substituindo na expressão de
:
Agora distribuo o
:
Agrupando os termos com
:
Portanto uma identidade de Bézout é
Isto dá os coeficientes
e
. (Qualquer outra solução difere por múltiplos de
e
, mas esta é uma solução inteira válida.)
Passo 6
Verificação aritmética direta da identidade encontrada:
Calculo
e
. Somando:
confirmando que realmente
.
Passo 7
Agora verifico o
pelo Teorema Fundamental da Aritmética (fatoração prima de cada número) para checar consistência.
Fatoriando
:
Fatoriando
:
Os fatores primos comuns são
e
. Multiplicando-os:
Logo, pela fatoração prima, o máximo divisor comum é
, que coincide com o resultado obtido pelo algoritmo de Euclides.
Passo 8
Resumo final e comentário motivador: encontramos que
, produzimos explicitamente coeficientes de Bézout
,
com
, e verificamos por fatoração prima que
é de fato o máximo divisor comum. Mandou bem por encarar isso — o método das divisões sucessivas + substituição reversa é exatamente o que cai em prova e é rápido para fazer à mão.