Sejam
. Mostre que a equação:
possui soluções inteiras se, e somente se,
.
Dica: use o resultado da questão 10.
Dica: use o resultado da questão 10.
Passo 1
O enunciado dá os inteiros
e pede para mostrar que a equação
tem solução inteira (isto é, existe
satisfazendo a igualdade) se, e somente se,
Aqui
denota o máximo divisor comum (mdc, ou gcd) dos
. A tarefa é provar as duas direções: (1) necessidade: se existe solução inteira então o mdc divide
; (2) suficiência: se o mdc divide
então existe solução inteira.
Passo 2
Explicando a notação e uma ideia-chave que será usada várias vezes.
- Significado de
: é o maior inteiro positivo que divide todos os . - Propriedade simples e útil: se um inteiro
divide cada , então divide qualquer combinação linear inteira com . Isso porque dividir cada termo implica dividir a soma. Vou usar isso para a direção “necessidade”. - Outro fato essencial (Lema de Bézout generalizado): existem inteiros
tais que
Vou demonstrar esse fato por indução (é a questão 10 a que o enunciado se refere, mas vou relembrar o argumento).
Passo 3
Prova da direção “necessidade” (mais simples).
Suponha que exista solução inteira
de
Se
, então por definição
divide cada
. Pela propriedade mencionada no passo 2,
divide a combinação linear à direita, logo
divide
. Portanto
Isto prova a necessidade: solução inteira implica
.
Passo 4
Prova do Lema de Bézout generalizado (existem
com
) — demonstração por indução em
.
Base
: óbvia, pois
.
Passo indutivo: suponha verdadeiro para
inteiros. Defina
Pela hipótese de indução existem inteiros
tais que
Agora aplique o caso
(o lema de Bézout para dois inteiros) aos inteiros
e
: existe uma combinação inteira
para alguns inteiros
. Mas
é exatamente
. Substituindo a expressão de
em termos dos
obtém-se
Portanto tomamos
para
e
, obtendo inteiros
com
Isso completa a prova do lema por indução (o caso
usado é o lema clássico provado pelo algoritmo de Euclides).
Passo 5
Prova da direção “suficiência” usando o Lema de Bézout.
Seja
. Pelas contas do passo 4 existem inteiros
tais que
Agora suponha que
. Então existe inteiro
tal que
. Multiplicando a identidade acima por
obtém-se
Como cada
é inteiro, isto fornece uma solução inteira explícita da equação original: basta tomar
Portanto, se
então a equação tem solução inteira.
Passo 6
Conclusão final das duas direções.
Juntando o passo 3 (necessidade) e o passo 5 (suficiência) obtemos a equivalência desejada: a equação
tem solução em inteiros se, e somente se,
Resposta
A equação
possui soluções inteiras se, e somente se,
.