Sejam a_{1}, a_{2}, \ldots, a_{n} \in \mathbb{Z}. Mostre que a equação: a_{1} X_{1}+a_{2} X_{2}+\cdots+a_{n} X_{n}=c possui soluções inteiras se, e somente se, \left(a_{1}, a_{2}, \ldots, a_{n}\right) \mid c.
Dica: use o resultado da questão 10.

Passo 1

O enunciado dá os inteiros a_{1},a_{2},\ldots,a_{n}\in\mathbb{Z} e pede para mostrar que a equação
a_{1}X_{1}+a_{2}X_{2}+\cdots+a_{n}X_{n}=c
tem solução inteira (isto é, existe (X_{1},\dots,X_{n})\in\mathbb{Z}^{n} satisfazendo a igualdade) se, e somente se,
\left(a_{1},a_{2},\ldots,a_{n}\right)\mid c.
Aqui \left(a_{1},a_{2},\ldots,a_{n}\right) denota o máximo divisor comum (mdc, ou gcd) dos a_{i}. A tarefa é provar as duas direções: (1) necessidade: se existe solução inteira então o mdc divide c; (2) suficiência: se o mdc divide c então existe solução inteira.

Passo 2

Explicando a notação e uma ideia-chave que será usada várias vezes.
  • Significado de \left(a_{1},\ldots,a_{n}\right)=d: é o maior inteiro positivo que divide todos os a_{i}.
  • Propriedade simples e útil: se um inteiro d divide cada a_{i}, então d divide qualquer combinação linear inteira \sum_{i} a_{i}x_{i} com x_{i}\in\mathbb{Z}. 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 u_{1},\dots,u_{n} tais que
\left(a_{1},\ldots,a_{n}\right)=a_{1}u_{1}+\cdots+a_{n}u_{n}.
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 (X_{1},\dots,X_{n})\in\mathbb{Z}^{n} de
a_{1}X_{1}+\cdots+a_{n}X_{n}=c.
Se d=\left(a_{1},\ldots,a_{n}\right), então por definição d divide cada a_{i}. Pela propriedade mencionada no passo 2, d divide a combinação linear à direita, logo d divide c. Portanto
\left(a_{1},\ldots,a_{n}\right)\mid c.
Isto prova a necessidade: solução inteira implica d\mid c.

Passo 4

Prova do Lema de Bézout generalizado (existem u_{i}\in\mathbb{Z} com \sum a_{i}u_{i}=d) — demonstração por indução em n.
Base n=1: óbvia, pois (a_{1})=|a_{1}|=a_{1}\cdot\operatorname{sgn}(a_{1}).
Passo indutivo: suponha verdadeiro para n-1 inteiros. Defina
d_{n-1}=\left(a_{1},\ldots,a_{n-1}\right).
Pela hipótese de indução existem inteiros v_{1},\dots,v_{n-1} tais que
d_{n-1}=a_{1}v_{1}+\cdots+a_{n-1}v_{n-1}.
Agora aplique o caso n=2 (o lema de Bézout para dois inteiros) aos inteiros d_{n-1} e a_{n}: existe uma combinação inteira
\left(d_{n-1},a_{n}\right)=d_{n-1}s + a_{n}t
para alguns inteiros s,t. Mas \left(d_{n-1},a_{n}\right) é exatamente \left(a_{1},\ldots,a_{n}\right). Substituindo a expressão de d_{n-1} em termos dos a_{i} obtém-se
\left(a_{1},\ldots,a_{n}\right) = \bigl(a_{1}v_{1}+\cdots+a_{n-1}v_{n-1}\bigr)s + a_{n}t = a_{1}(v_{1}s)+\cdots+a_{n-1}(v_{n-1}s)+a_{n}t.
Portanto tomamos u_{i}=v_{i}s para i\le n-1 e u_{n}=t, obtendo inteiros u_{1},\dots,u_{n} com
\left(a_{1},\ldots,a_{n}\right)=a_{1}u_{1}+\cdots+a_{n}u_{n}.
Isso completa a prova do lema por indução (o caso n=2 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 d=\left(a_{1},\ldots,a_{n}\right). Pelas contas do passo 4 existem inteiros u_{1},\dots,u_{n} tais que
d=a_{1}u_{1}+\cdots+a_{n}u_{n}.
Agora suponha que d\mid c. Então existe inteiro k tal que c=kd. Multiplicando a identidade acima por k obtém-se
c = k d = a_{1}(k u_{1})+\cdots+a_{n}(k u_{n}).
Como cada k u_{i} é inteiro, isto fornece uma solução inteira explícita da equação original: basta tomar
X_{i}=k u_{i}\quad\text{para }i=1,\dots,n.
Portanto, se d\mid c 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
a_{1}X_{1}+\cdots+a_{n}X_{n}=c
tem solução em inteiros se, e somente se,
\left(a_{1},\ldots,a_{n}\right)\mid c.

Resposta

A equação a_{1}X_{1}+a_{2}X_{2}+\cdots+a_{n}X_{n}=c possui soluções inteiras se, e somente se, \left(a_{1},a_{2},\ldots,a_{n}\right)\mid c.

Exercícios relacionados