Use o algoritmo de Euclides para obter números r e s satisfazendo 135 r+308 s=-4

Passo 1

O enunciado pede que a gente encontre números inteiros r e s tais que
135\,r + 308\,s = -4.
Informações dadas:
\text{os inteiros }135\text{ e }308\quad\text{e o lado direito }-4.
Objetivo imediato: usar o algoritmo de Euclides estendido para escrever -4 como combinação linear de 135 e 308 e assim obter r e s.

Passo 2

Vou aplicar o algoritmo de Euclides para achar o \gcd(135,308). Lembra: o algoritmo faz divisões sucessivas para obter restos até o resto ser 0; o último resto não-nulo é o \gcd. Faço as divisões:
308 = 2\cdot135 + 38
135 = 3\cdot38 + 21
38 = 1\cdot21 + 17
21 = 1\cdot17 + 4
17 = 4\cdot4 + 1
4 = 4\cdot1 + 0

Passo 3

Do passo anterior o último resto não-nulo é 1. Portanto
\gcd(135,308) = 1.
Isso é ótimo: como 1 divide -4, existe solução inteira para 135\,r+308\,s=-4. Nosso próximo objetivo é expressar 1 como combinação linear 1=135\cdot a + 308\cdot b (a partir da decomposição acima) e depois multiplicar por -4 para obter os coeficientes procurados.

Passo 4

Agora faço a substituição regressiva (Euclides estendido) para escrever 1 como combinação de 135 e 308.
Começo com a última divisão não-trivial:
1 = 17 - 4\cdot4.
Mas da divisão anterior temos
4 = 21 - 1\cdot17,
substituindo:
1 = 17 - 4\cdot(21 - 17) = 17 -4\cdot21 +4\cdot17 = 5\cdot17 -4\cdot21.
Agora uso 17 = 38 - 1\cdot21:
1 = 5\cdot(38 - 21) -4\cdot21 = 5\cdot38 -5\cdot21 -4\cdot21 = 5\cdot38 -9\cdot21.
Em seguida uso 21 = 135 - 3\cdot38:
1 = 5\cdot38 -9\cdot(135 -3\cdot38) = 5\cdot38 -9\cdot135 +27\cdot38 = 32\cdot38 -9\cdot135.
Por fim uso 38 = 308 - 2\cdot135:
1 = 32\cdot(308 -2\cdot135) -9\cdot135 = 32\cdot308 -64\cdot135 -9\cdot135 = 32\cdot308 -73\cdot135.
Assim encontramos uma expressão para 1:
1 = (-73)\cdot135 + 32\cdot308.

Passo 5

Multiplico a expressão de 1 por -4 para obter -4:
-4 = -4\cdot 1 = -4\cdot\bigl((-73)\cdot135 + 32\cdot308\bigr).
Distribuindo:
-4 = ( -4\cdot -73)\cdot135 + (-4\cdot 32)\cdot308 = 292\cdot135 + (-128)\cdot308.
Portanto uma solução inteira é r = 292 e s = -128.

Resposta

r=292,\; s=-128

Exercícios relacionados