[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.
Passo 1
O enunciado pede para decidir se a equação diofantina
tem solução inteira. As informações importantes que temos são os coeficientes
e
e o termo independente
. Queremos saber se existem inteiros
e
que satisfaçam essa igualdade.
Passo 2
Regra prática (que vamos justificar depois): a equação linear diofantina
tem solução inteira se, e somente se,
divide
. Então o primeiro passo é calcular
usando o algoritmo de Euclides.
Executando o algoritmo de Euclides:
Quando o resto chega a zero, o último resto não nulo é o máximo divisor comum. Portanto
Passo 3
Agora explico por que usamos esse
. Primeiro, qualquer combinação linear
é múltiplo do
. Em linguagem simples: se
, então
divide
e
, logo divide
e
para quaisquer inteiros
; assim
divide
. Portanto, se existir solução inteira para
então
tem que dividir
. 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
tais que
Multiplicando por
(quando
) obtemos uma solução para
. Esses
podem ser obtidos pelo processo inverso do algoritmo de Euclides (algoritmo de Euclides estendido). Vamos até achar esses
no nosso caso para aprender o método: voltamos às igualdades obtidas no algoritmo e expressamos o último resto não nulo (
) como combinação de
e
.
Da primeira linha:
Da segunda linha:
Substituindo
na segunda:
Assim encontramos inteiros
e
tais que
Passo 4
Voltemos à equação original. Já vimos que
. Para que existisse solução inteira deveríamos ter
. Mas
dividido por
não é inteiro:
. Portanto é impossível que inteiros
satisfaçam
, porque o lado esquerdo sempre seria múltiplo de
enquanto o lado direito
não é múltiplo de
. Conclusão: não existem soluções inteiras.
Passo 5
Só para consolidar o aprendizado: se em vez de
tivéssemos um
múltiplo de
(por exemplo
), então multiplicando a identidade de Bézout que achamos por
obteríamos uma solução particular. No nosso caso específico, se
temos a solução particular
porque
. E quando existe uma solução particular
, todas as soluções inteiras são dadas pela fórmula paramétrica
com
. Assim há infinitas soluções (uma para cada
) sempre que
divide
.
Resposta
Não há solução inteira, pois
não divide
.