Questão 07: Encontre todas as possíveis soluções para
1001 x+109 y=(1001,109)

Passo 1

O enunciado pede para resolver em \mathbb{Z} a equação
1001x + 109y = (1001,109),
onde (1001,109) é o máximo divisor comum de 1001 e 109. Vamos usar o algoritmo de Euclides para achar o mdc e depois o algoritmo de Euclides estendido para obter uma solução particular e, por fim, a família de soluções.

Passo 2

Aplicando o algoritmo de Euclides para calcular \gcd(1001,109):
1001 = 109 \cdot 9 + 20
109 = 20 \cdot 5 + 9
20 = 9 \cdot 2 + 2
9 = 2 \cdot 4 + 1
2 = 1 \cdot 2 + 0
Logo
\gcd(1001,109) = 1.

Passo 3

Agora fazemos a retro-substituição para escrever 1 como combinação linear de 1001 e 109:
1 = 9 - 2\cdot4 = 9 - 4\cdot\bigl(20 - 9\cdot2\bigr) = 9\cdot9 - 20\cdot4
= \bigl(109 - 5\cdot20\bigr)\cdot9 - 20\cdot4 = 109\cdot9 - 20\cdot49
= 109\cdot9 - \bigl(1001 - 109\cdot9\bigr)\cdot49 = -1001\cdot49 + 109\cdot450.
Isso mostra que (x_0,y_0)=(-49,450) é uma solução particular de
1001x + 109y = 1.

Passo 4

Como o mdc é 1, a solução geral da equação diofantina
1001x + 109y = 1
é dada por
x = x_0 + \frac{109}{1}\,t = -49 + 109\,t, \quad y = y_0 - \frac{1001}{1}\,t = 450 - 1001\,t,
com t\in\mathbb{Z}.

Resposta

A família de soluções inteiras de
1001x + 109y = (1001,109)
é
x = -49 + 109\,t,\quad y = 450 - 1001\,t,\quad t\in\mathbb{Z}.

Exercícios relacionados