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 s \cdot 420+\mathrm{t} \cdot 156=m d c(420,156).

Passo 1

O enunciado pede três coisas:
  1. (a) Calcular \operatorname{mdc}(420,156) usando o algoritmo de Euclides.
  2. (b) Escrever esse \operatorname{mdc} como combinação linear de 420 e 156; ou seja, encontrar inteiros s e t tais que s\cdot420 + t\cdot156 = \operatorname{mdc}(420,156).
  3. (c) Verificar que os s e t encontrados satisfazem a equação do item (b).
Informações dadas: os dois números 420 e 156. Nada mais é pedido.

Passo 2

Breve explicação do método que vamos usar (passo didático): o algoritmo de Euclides calcula o \operatorname{mdc} 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 \operatorname{mdc}. Vou aplicar isso passo a passo.

Passo 3

Façamos as divisões do algoritmo de Euclides entre \,420 e \,156.
420 = 2\cdot156 + 108
156 = 1\cdot108 + 48
108 = 2\cdot48 + 12
48 = 4\cdot12 + 0
Aqui o resto tornou-se zero na última linha, portanto o último resto não nulo é 12.

Passo 4

Conclusão do algoritmo: o \operatorname{mdc} é o último resto não nulo que encontramos.
\operatorname{mdc}(420,156)=12
Explicação rápida: como 48 = 4\cdot12 e o resto seguinte é zero, 12 divide 48 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 s e t tais que s\cdot420+t\cdot156=12) usando retro-substituição nas igualdades do algoritmo. Primeiro, escrevemos as igualdades obtidas isolando cada resto:
108 = 420 - 2\cdot156
48 = 156 - 1\cdot108
12 = 108 - 2\cdot48

Passo 6

Substituímos a expressão de 48 na expressão de 12 para escrever 12 em termos de 108 e 156.
Começando de
12 = 108 - 2\cdot48
e usando
48 = 156 - 1\cdot108,
temos
12 = 108 - 2\cdot(156 - 1\cdot108).
Desenvolvendo a multiplicação:
12 = 108 - 2\cdot156 + 2\cdot108.
Somando os termos em 108:
12 = 3\cdot108 - 2\cdot156.

Passo 7

Agora substituímos a expressão de 108 em termos de 420 e 156. Usamos
108 = 420 - 2\cdot156.
Substituindo em
12 = 3\cdot108 - 2\cdot156,
obtemos
12 = 3\cdot(420 - 2\cdot156) - 2\cdot156.
Desenvolvendo:
12 = 3\cdot420 - 6\cdot156 - 2\cdot156.
12 = 3\cdot420 - 8\cdot156.
Portanto uma combinação linear que dá 12 é 3\cdot420 + (-8)\cdot156.

Passo 8

Interpretação didática do resultado: os inteiros de Bézout são s=3 e t=-8. Isso significa que o \operatorname{mdc} é 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.
3\cdot420 = 1260
(-8)\cdot156 = -1248
Somando:
1260 + (-1248) = 12.
Isso confirma que 3\cdot420 + (-8)\cdot156 = 12, ou seja, a relação está satisfeita.

Resposta

(a) \operatorname{mdc}(420,156)=12
(b) 12 = 3\cdot420 + (-8)\cdot156
(c) Verificação: 3\cdot420 + (-8)\cdot156 = 1260 - 1248 = 12

Exercícios relacionados