1. Combinação Linear e Algoritmo de Euclides
(a) Use o algoritmo de Euclides para encontrar mdc(420,156).
(b) Expresse esse mdc como uma combinação linear de 420 e 156.
(c) Verifique se o resultado satisfaz a equação
.
(b) Expresse esse mdc como uma combinação linear de 420 e 156.
(c) Verifique se o resultado satisfaz a equação
Passo 1
O enunciado pede três coisas:
- (a) Calcular
usando o algoritmo de Euclides. - (b) Escrever esse
como combinação linear de e ; ou seja, encontrar inteiros e tais que . - (c) Verificar que os
e encontrados satisfazem a equação do item (b).
Informações dadas: os dois números
e
. Nada mais é pedido.
Passo 2
Breve explicação do método que vamos usar (passo didático): o algoritmo de Euclides calcula o
fazendo divisões sucessivas com resto. Em cada passo dividimos o maior pelo menor, registramos quociente e resto, e repetimos usando o divisor e o resto até obter resto zero. O último resto não nulo é o
. Vou aplicar isso passo a passo.
Passo 3
Façamos as divisões do algoritmo de Euclides entre
e
.
Aqui o resto tornou-se zero na última linha, portanto o último resto não nulo é
.
Passo 4
Conclusão do algoritmo: o
é o último resto não nulo que encontramos.
Explicação rápida: como
e o resto seguinte é zero,
divide
e também divide todos os restos anteriores, sendo o maior divisor comum.
Passo 5
Agora vamos obter os coeficientes de Bézout (os inteiros
e
tais que
) usando retro-substituição nas igualdades do algoritmo. Primeiro, escrevemos as igualdades obtidas isolando cada resto:
Passo 6
Substituímos a expressão de
na expressão de
para escrever
em termos de
e
.
Começando de
e usando
temos
Desenvolvendo a multiplicação:
Somando os termos em
:
Passo 7
Agora substituímos a expressão de
em termos de
e
. Usamos
Substituindo em
obtemos
Desenvolvendo:
Portanto uma combinação linear que dá
é
.
Passo 8
Interpretação didática do resultado: os inteiros de Bézout são
e
. Isso significa que o
é uma combinação inteira dos números dados, como prometido pelo Teorema de Bézout.
Passo 9
Verificação numérica explícita (para o item (c)): calculemos os produtos e a soma para checar.
Somando:
Isso confirma que
, ou seja, a relação está satisfeita.
Resposta
(a)
(b)
(c) Verificação:
(b)
(c) Verificação: