Use o algoritmo euclidiano para encontrar: m d c(102,222) e m d c(666,1414). Escreva o m d c, como combinação linear desses inteiros.

Passo 1

O enunciado nos pede para calcular o máximo divisor comum, isto é \gcd, de cada par de inteiros (102,222) e (666,1414) usando o algoritmo de Euclides, e em seguida expressar cada \gcd como combinação linear dos dois inteiros correspondentes. O conteúdo envolvido é o algoritmo de Euclides e o algoritmo estendido para obter a combinação linear.

Passo 2

Aplicando o algoritmo de Euclides em 102 e 222:
222 = 102 \cdot 2 + 18
102 = 18 \cdot 5 + 12
18 = 12 \cdot 1 + 6
12 = 6 \cdot 2 + 0
Como o resto chegou a zero, o último resto não nulo é
\gcd(102,222) = 6.

Passo 3

Agora estendemos para escrever 6 como combinação linear de 102 e 222. Partimos da penúltima linha:
6 = 18 - 12 \cdot 1.
Mas 12 e 18 vêm das linhas anteriores:
12 = 102 - 18 \cdot 5, \quad 18 = 222 - 102 \cdot 2.
Substituindo sucessivamente,
6 = 18 - (102 - 18\cdot5) = 18\cdot6 - 102,
6 = (222 - 102\cdot2)\cdot6 - 102 = 222\cdot6 - 102\cdot12 - 102 = 222\cdot6 - 102\cdot13.
Logo,
6 = -13 \cdot 102 \;+\; 6 \cdot 222.

Passo 4

Aplicando o algoritmo de Euclides em 666 e 1414:
1414 = 666 \cdot 2 + 82
666 = 82 \cdot 8 + 10
82 = 10 \cdot 8 + 2
10 = 2 \cdot 5 + 0
Logo,
\gcd(666,1414) = 2.

Passo 5

Para a combinação linear de 2, partimos de
2 = 82 - 10 \cdot 8.
E temos
10 = 666 - 82 \cdot 8, \quad 82 = 1414 - 666 \cdot 2.
Substituindo em cadeia:
2 = 82 - (666 - 82\cdot8)\cdot8 = 82\cdot65 - 666\cdot8,
2 = (1414 - 666\cdot2)\cdot65 - 666\cdot8 = 1414\cdot65 - 666\cdot130 - 666\cdot8 = 1414\cdot65 - 666\cdot138.
Logo,
2 = -138 \cdot 666 \;+\; 65 \cdot 1414.

Resposta

\gcd(102,222) = 6, e 6 = -13 \cdot 102 + 6 \cdot 222. \gcd(666,1414) = 2, e 2 = -138 \cdot 666 + 65 \cdot 1414.

Exercícios relacionados