[Fácil] Decida, usando o mdc obtido pelo algoritmo de Euclides, se as equações diofantinas a seguir têm solução inteira. Quando houver solução, explique por que há infinitas soluções.
77 x+91 y=7

Passo 1

O enunciado pede para decidir, usando o mdc obtido pelo algoritmo de Euclides, se a equação diofantina
77x + 91y = 7
tem solução inteira. Quando houver solução, devo explicar por que existem infinitas soluções.
Dados relevantes do enunciado:
  • Coeficientes: 77 e 91.
  • Termo independente: 7.
  • Queremos soluções inteiras (x,y)\in\mathbb{Z}^2.
  • Devemos usar o algoritmo de Euclides para obter o \gcd(77,91).

Passo 2

Calcular o \gcd(77,91) pelo algoritmo de Euclides (divisões sucessivas). Vou fazer as divisões e anotar os restos:
91 = 77\cdot 1 + 14
77 = 14\cdot 5 + 7
14 = 7\cdot 2 + 0
Quando o resto é 0, o último resto não nulo é o \gcd. Portanto
\gcd(77,91)=7.
Explicação curta do porquê fiz isso: o algoritmo de Euclides repete divisões euclidianas até o resto ser zero; o último resto não nulo é o máximo divisor comum.

Passo 3

Usar a condição necessária e suficiente para existência de solução inteira da equação linear ax+by=c:
Teorema (em palavras simples): A equação ax+by=c tem solução inteira se, e somente se, \gcd(a,b) divide c.
Motivo: todo número da forma ax+by é múltiplo de \gcd(a,b); portanto se existe solução precisa ter \gcd(a,b)\mid c. Reciprocamente, se \gcd(a,b)\mid c então dividindo toda a equação por d=\gcd(a,b) reduz-se a caso onde os coeficientes são coprimos, e então o algoritmo extendido de Euclides fornece uma combinação linear que iguala 1, multiplicando depois por c/d dá uma solução.
No nosso caso temos d=\gcd(77,91)=7 e o termo independente é 7. Como 7 divide 7, a condição é satisfeita. Conclusão inicial: existem soluções inteiras.

Passo 4

Agora vamos encontrar uma solução particular usando o algoritmo de Euclides estendido (retro-substituição nas divisões que fizemos).
Das divisões anteriores eu tenho:
14 = 91 - 77\cdot 1.
E
7 = 77 - 14\cdot 5.
Substituo a expressão de 14 na expressão de 7:
7 = 77 - 5\cdot(91 - 77\cdot 1).
Distribuindo e juntando termos de 77 e 91:
7 = 77 -5\cdot 91 +5\cdot 77 = (1+5)\cdot 77 + (-5)\cdot 91.
Logo
7 = 6\cdot 77 + (-5)\cdot 91,
ou seja
77\cdot 6 + 91\cdot (-5) = 7.
Isso nos dá uma solução particular:
x_0 = 6,\qquad y_0 = -5.

Passo 5

Derivar a solução geral inteira e explicar por que há infinitas soluções.
Fatos padrão (e fáceis de verificar): se (x_0,y_0) é uma solução particular de ax+by=c e d=\gcd(a,b), então todas as soluções inteiras são dadas por
x = x_0 + \frac{b}{d}\,t,\qquad y = y_0 - \frac{a}{d}\,t,
onde t é qualquer inteiro ( t\in\mathbb{Z}). Isso funciona porque
a\left(x_0+\frac{b}{d}t\right)+b\left(y_0-\frac{a}{d}t\right) = ax_0+by_0 + \left(a\frac{b}{d}-b\frac{a}{d}\right)t = c.
No nosso caso a=77, b=91, d=7. Então
\frac{b}{d}=\frac{91}{7}=13,\qquad \frac{a}{d}=\frac{77}{7}=11.
Usando a solução particular (x_0,y_0)=(6,-5), a solução geral inteira é
x = 6 + 13t,\qquad y = -5 - 11t,\qquad t\in\mathbb{Z}.
Por que são infinitas soluções? Porque t pode ser qualquer inteiro e cada valor distinto de t produz um par (x,y) inteiro diferente; não há restrição sobre t. Assim há uma família infinita de soluções.
Exemplo rápido para conferir: para t=0 recuperamos (6,-5). Para t=1 obtemos (19,-16) e de fato
77\cdot 19 + 91\cdot(-16) = 1463 - 1456 = 7.

Resposta

Há solução inteira.
Uma solução particular é x=6,\\ y=-5.
Todas as soluções inteiras são x=6+13t,\\ y=-5-11t, t\in\mathbb{Z}.

Exercícios relacionados