[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=10

Passo 1

O enunciado pede para decidir se a equação diofantina
77x + 91y = 10
tem solução inteira. As informações importantes que temos são os coeficientes 77 e 91 e o termo independente 10. Queremos saber se existem inteiros x e y que satisfaçam essa igualdade.

Passo 2

Regra prática (que vamos justificar depois): a equação linear diofantina
ax+by=c
tem solução inteira se, e somente se, \gcd(a,b) divide c. Então o primeiro passo é calcular \gcd(77,91) usando o algoritmo de Euclides.
Executando o algoritmo de Euclides:
91 = 77\cdot1 + 14
77 = 14\cdot5 + 7
14 = 7\cdot2 + 0
Quando o resto chega a zero, o último resto não nulo é o máximo divisor comum. Portanto
\gcd(77,91)=7.

Passo 3

Agora explico por que usamos esse \gcd. Primeiro, qualquer combinação linear 77x+91y é múltiplo do \gcd(77,91). Em linguagem simples: se d=\gcd(77,91), então d divide 77 e 91, logo divide 77x e 91y para quaisquer inteiros x,y; assim d divide 77x+91y. Portanto, se existir solução inteira para
77x+91y=10,
então d tem que dividir 10. Isso já dá uma condição necessária.
A condição também é suficiente: existe o Teorema de Bézout que diz que existem inteiros u,v tais que
77u + 91v = d.
Multiplicando por c/d (quando d\mid c) obtemos uma solução para 77x+91y=c. Esses u,v podem ser obtidos pelo processo inverso do algoritmo de Euclides (algoritmo de Euclides estendido). Vamos até achar esses u,v no nosso caso para aprender o método: voltamos às igualdades obtidas no algoritmo e expressamos o último resto não nulo ( 7) como combinação de 77 e 91.
Da primeira linha:
14 = 91 - 77\cdot1.
Da segunda linha:
7 = 77 - 14\cdot5.
Substituindo 14 na segunda:
7 = 77 - (91 - 77\cdot1)\cdot5 = 77 -5\cdot91 +5\cdot77 = 6\cdot77 -5\cdot91.
Assim encontramos inteiros u=6 e v=-5 tais que
77\cdot6 + 91\cdot(-5) = 7.

Passo 4

Voltemos à equação original. Já vimos que \gcd(77,91)=7. Para que existisse solução inteira deveríamos ter 7\mid 10. Mas 10 dividido por 7 não é inteiro: 7\nmid 10. Portanto é impossível que inteiros x,y satisfaçam 77x+91y=10, porque o lado esquerdo sempre seria múltiplo de 7 enquanto o lado direito 10 não é múltiplo de 7. Conclusão: não existem soluções inteiras.

Passo 5

Só para consolidar o aprendizado: se em vez de 10 tivéssemos um c múltiplo de 7 (por exemplo c=14), então multiplicando a identidade de Bézout que achamos por c/7 obteríamos uma solução particular. No nosso caso específico, se c=14 temos a solução particular
x_0 = 6\cdot\frac{14}{7}=12,\qquad y_0 = -5\cdot\frac{14}{7}=-10,
porque 77\cdot12 + 91\cdot(-10)=14. E quando existe uma solução particular (x_0,y_0), todas as soluções inteiras são dadas pela fórmula paramétrica
x = x_0 + \frac{91}{7}\,t = x_0 + 13t,\qquad y = y_0 - \frac{77}{7}\,t = y_0 - 11t,
com t\in\mathbb{Z}. Assim há infinitas soluções (uma para cada t) sempre que d=\gcd(a,b) divide c.

Resposta

Não há solução inteira, pois \gcd(77,91)=7 não divide 10.

Exercícios relacionados