a) Resolva a equação diofantina 7 x+19 y=1921.
b) Determine em IN \times \mathbb{I N}) a solução ( x0, y0 ) cuja soma x0+y0 seja a menor possível.

Passo 1

O enunciado pede duas coisas:
  1. Resolver a equação diofantina linear
7x + 19y = 1921
isto é, achar todas as soluções inteiras (x,y).
2. Entre as soluções com x,yinN, escolher aquela cuja soma x+y seja mínima.
Para isso, vamos usar o Algoritmo de Euclides Estendido, obter uma solução particular, escrever a solução geral e depois impor x>=0, y>=0 para encontrar o par de soma mínima.

Passo 2

Aplicamos o Algoritmo de Euclides para 19 e 7:
19 = 2cdot7 + 5,
7 = 1cdot5 + 2,
5 = 2cdot2 + 1
Reescrevendo o resto 1 como combinação de 7 e 19:
1 = 5 - 2cdot2 = 5 - 2,(7 - 1cdot5) = 3cdot5 - 2cdot7 = 3,(19 - 2cdot7) - 2cdot7 = 3cdot19 - 8cdot7
Logo uma solução de
7u + 19v = 1
é
u = -8, v = 3

Passo 3

Multiplicando essa identidade por 1921, obtemos uma solução particular de
7x + 19y = 1921:
xp = -8cdot1921 = -15368, yp = 3cdot1921 = 5763
Como a solução geral da diofantina 7x+19y=1921 é
x = xp + 19t = -15368 + 19t, y = yp - 7t = 5763 - 7t, tinZ,
isso resolve a parte (a).

Passo 4

Para a parte (b) impomos x>=0 e y>=0:
-15368 + 19t >= 0 Longrightarrow t >= 1536819 approx 808,84 Longrightarrow t>=809,
5763 - 7t >= 0 Longrightarrow t <= 57637 approx 823,29 Longrightarrow t<=823
Logo tin809,810,dots,823.

Passo 5

Definimos a soma
S(t) = x+y = (-15368 + 19t) + (5763 -7t) = -9605 +12t
Como 12>0, S(t) cresce quando t cresce. Logo a soma é mínima para o menor t, que é t=809. Substituindo:
x0 = -15368 + 19cdot809 = 3, y0 = 5763 - 7cdot809 = 100

Resposta

a) As soluções inteiras são
(x,y) = l(-15368 + 19t,;5763 -7tr), tinZ
b) Em NtimesN, a solução de soma mínima é
(x0,y0) = (3,,100)

Exercícios de Livros Relacionados