1. (2 pontos) Expresse o MDC de 34 e 55 como uma combinação linear destes inteiros.

Passo 1

O enunciado pede que eu expresse o MDC de 34 e 55 como uma combinação linear desses inteiros. Ou seja, quero encontrar inteiros x e y tais que
\gcd(34,55)=x\cdot34+y\cdot55.
Informações dadas: os dois inteiros 34 e 55. Pergunta: achar x e y e escrever a identidade acima.

Passo 2

Vou usar o algoritmo de Euclides para calcular o \gcd e depois o processo de retro-substituição (algoritmo estendido) para obter os coeficientes x e y. Antes de começar, rapidinho sobre a ideia (sem formalidade pesada): o algoritmo de Euclides aplica repetidas divisões com resto usando a propriedade de que \gcd(a,b)=\gcd(b,r) quando a=bq+r. A cada passo reduzimos o problema até obter resto 0; o último resto não nulo é o \gcd.

Passo 3

Faço as divisões sucessivas entre 55 e 34 e depois entre os pares que aparecem, guardando quocientes e restos:
55 = 1\cdot34 + 21
34 = 1\cdot21 + 13
21 = 1\cdot13 + 8
13 = 1\cdot8 + 5
8 = 1\cdot5 + 3
5 = 1\cdot3 + 2
3 = 1\cdot2 + 1
2 = 2\cdot1 + 0
O último resto não-nulo é 1, portanto \gcd(34,55)=1.

Passo 4

Agora vou escrever cada resto como combinação linear dos anteriores para, passo a passo, chegar a uma expressão de 1 em função de 34 e 55. Primeiro, reorganizo as igualdades acima para isolar os restos (vou numerar as igualdades para facilitar):
(1) \;21 = 55 - 1\cdot34
(2) \;13 = 34 - 1\cdot21
(3) \;8 = 21 - 1\cdot13
(4) \;5 = 13 - 1\cdot8
(5) \;3 = 8 - 1\cdot5
(6) \;2 = 5 - 1\cdot3
(7) \;1 = 3 - 1\cdot2
Começo a substituir da equação (7) para trás.

Passo 5

Substituo 2 usando (6) na (7):
Da (6): \;2 = 5 - 1\cdot3.
Substituindo em (7):
1 = 3 - 1\cdot(5 - 1\cdot3) = 3 - 1\cdot5 + 1\cdot3 = 2\cdot3 - 1\cdot5.
Portanto:
1 = 2\cdot3 - 1\cdot5.

Passo 6

Substituo 3 usando (5) onde 3 = 8 - 1\cdot5:
1 = 2\cdot(8 - 1\cdot5) - 1\cdot5 = 2\cdot8 - 2\cdot5 - 1\cdot5 = 2\cdot8 - 3\cdot5.
Portanto:
1 = 2\cdot8 - 3\cdot5.

Passo 7

Substituo 5 usando (4) onde 5 = 13 - 1\cdot8:
1 = 2\cdot8 - 3\cdot(13 - 1\cdot8) = 2\cdot8 - 3\cdot13 + 3\cdot8 = 5\cdot8 - 3\cdot13.
Portanto:
1 = 5\cdot8 - 3\cdot13.

Passo 8

Substituo 8 usando (3) onde 8 = 21 - 1\cdot13:
1 = 5\cdot(21 - 1\cdot13) - 3\cdot13 = 5\cdot21 - 5\cdot13 - 3\cdot13 = 5\cdot21 - 8\cdot13.
Portanto:
1 = 5\cdot21 - 8\cdot13.

Passo 9

Substituo 13 usando (2) onde 13 = 34 - 1\cdot21:
1 = 5\cdot21 - 8\cdot(34 - 1\cdot21) = 5\cdot21 - 8\cdot34 + 8\cdot21 = 13\cdot21 - 8\cdot34.
Portanto:
1 = 13\cdot21 - 8\cdot34.

Passo 10

Finalmente, substituo 21 usando (1) onde 21 = 55 - 1\cdot34:
1 = 13\cdot(55 - 1\cdot34) - 8\cdot34 = 13\cdot55 - 13\cdot34 - 8\cdot34 = 13\cdot55 - 21\cdot34.
Assim obtemos uma expressão de 1 como combinação linear de 34 e 55.

Resposta

1 = -21\cdot34 + 13\cdot55

Exercícios relacionados