Questão 05: Use o algoritmo de Euclides estendido para resolver a seguinte equação
119 x+272 y=(119,272)

Passo 1

O enunciado pede para usar o algoritmo de Euclides estendido para resolver a equação
119\,x+272\,y=(119,272).
O conteúdo envolve equações diofantinas lineares e cálculo de máximo divisor comum. Vamos primeiro determinar \gcd(119,272).

Passo 2

Aplicando o algoritmo de Euclides para \gcd(119,272):
272 = 2\cdot 119 + 34
119 = 3\cdot 34 + 17
34 = 2\cdot 17 + 0
Logo,
\gcd(119,272)=17.

Passo 3

Agora fazemos a retro-substituição para escrever 17 como combinação linear de 119 e 272. Primeiro,
17 = 119 - 3\cdot 34.
Mas
34 = 272 - 2\cdot 119.
Substituindo,
17 = 119 - 3\,(272 - 2\cdot 119) = 119 - 3\cdot 272 + 6\cdot 119 = 7\cdot 119 - 3\cdot 272.
Portanto, uma solução particular é
x_{0}=7,\quad y_{0}=-3.

Passo 4

Em toda equação diofantina a\,x+b\,y=d com \gcd(a,b)=d, a solução geral é
x = x_{0} + \frac{b}{d}\,t, \quad y = y_{0} - \frac{a}{d}\,t,
para t\in\mathbb{Z}. Aqui a=119, b=272 e d=17, logo
x = 7 + \frac{272}{17}\,t = 7 + 16\,t,
y = -3 - \frac{119}{17}\,t = -3 - 7\,t,
com t\in\mathbb{Z}.

Resposta

Uma solução particular é (x,y)=(7,-3).
A solução geral da equação
119\,x+272\,y=17
é
x=7+16\,t,\quad y=-3-7\,t,\quad t\in\mathbb{Z}.

Exercícios relacionados