Sejam a, b e c inteiros. Provar que:
(a) existem inteiros x e y tais que c=a x+b y se, e somente se, o m d c(a, b) \mid c.
(b) se existem inteiros x e y tais que a x+b y=m d c(a, b), então o m d c(x, y)=1.

Passo 1

O enunciado dá que a, b e c são inteiros e pede que mostremos duas coisas:
(a) Mostrar que existem inteiros x e y tais que c = a x + b y se, e somente se, \gcd(a,b)\mid c.
(b) Mostrar que, se existem inteiros x e y tais que a x + b y = \gcd(a,b), então \gcd(x,y)=1.
Informações relevantes fornecidas:
  • a,b,c\in\mathbb{Z}.
  • A função \gcd(\cdot,\cdot) significa o máximo divisor comum dos dois argumentos.
  • Precisamos provar uma equivalência na parte (a) (duas implicações) e uma propriedade de primitividade na parte (b).

Passo 2

Definição e observação útil (ferramenta básica). Seja
d=\gcd(a,b).
Por definição de máximo divisor comum, temos que d é um divisor comum de a e b (isto é, d\mid a e d\mid b) e qualquer outro divisor comum de a e b divide d. Uma propriedade imediata e muito usada: se d\mid a e d\mid b então d divide qualquer combinação linear a x + b y para inteiros x,y. Vou usar essa propriedade para provar uma das direções da parte (a).
Prova da implicação direta de (a): se existem inteiros x,y tais que c=a x+b y, então d\mid c.
Raciocínio: como d\mid a e d\mid b, qualquer combinação linear a x + b y é múltiplo de d. Assim, se c=a x+b y então d\mid c. Exemplo concreto para ver a ideia: se d=3, a=6, b=9, então qualquer 6x+9y é múltiplo de 3.

Passo 3

Agora a implicação recíproca de (a): se d\mid c então existem inteiros x,y tais que c=a x+b y.
Estratégia: primeiro provar que existem inteiros s,t tais que
a s + b t = d.
Isto é o lema de Bézout; apresento uma prova construtiva (padrão) usando o argumento do menor elemento positivo num conjunto de combinações lineares.
Defina o conjunto
S=\{\,a u + b v \mid u,v\in\mathbb{Z},\\ a u + b v >0\,\}.
Primeiro, S não é vazio: por exemplo, usando a identidade trivial a\cdot 1 + b\cdot 0 = a ou a\cdot 0 + b\cdot 1 = b, se ao menos um entre a e b for não nulo obtemos um elemento \neq 0; se ambos são zeros o enunciado é trivial (caso a=b=0 tem-se \gcd(0,0) indefinido, mas normalmente o contexto pressupõe que nem ambos são zero). Como S é um subconjunto dos inteiros positivos e não vazio, ele tem um menor elemento; chame-o de m. Pelo modo como S foi definido, existem inteiros s,t tais que
m = a s + b t.
Agora provamos que m é divisor comum de a e b. Divida a por m: existem inteiros q e r com 0\le r<m tais que
a = q m + r.
Reescrevendo r em termos de a,b:
r = a - q m = a - q(a s + b t) = a(1 - q s) + b(-q t),
portanto r é da forma a u + b v. Como 0\le r < m e m é o menor número positivo da forma a u + b v, a única possibilidade é r=0. Assim m\mid a. Pelo mesmo argumento com b obtemos m\mid b. Então m é um divisor comum de a e b.
Como d=\gcd(a,b) é o maior divisor comum, temos m\le d. Por outro lado, qualquer divisor comum (em particular d) divide qualquer combinação linear; logo d\mid m. Daí d\le m. Juntando as duas desigualdades obtemos m=d. Em particular existe representação de Bézout:
a s + b t = d
para certos inteiros s,t.

Passo 4

Concluir a recíproca de (a) usando a representação de Bézout.
Se d\mid c, escreva c=d\cdot k com k\in\mathbb{Z}. Como já provamos que existem s,t\in\mathbb{Z} com a s + b t = d, basta multiplicar essa igualdade por k:
a (k s) + b (k t) = d k = c.
Portanto x=k s e y=k t são inteiros que satisfazem c=a x + b y. Isso mostra que a condição d\mid c implica existência de solução inteira. Juntando com o resultado do Passo 2 (que mostrou a outra direção) concluímos a equivalência pedida em (a).
Resumo da ideia: todo divisor comum divide todas as combinações lineares; e existe uma combinação linear que é exatamente o \gcd, então multiplicando-a obtém-se qualquer múltiplo do \gcd.

Passo 5

Prova de (b). Queremos mostrar: se existem inteiros x,y tais que
a x + b y = d
com d=\gcd(a,b), então \gcd(x,y)=1.
Argumento direto simples e elegante: divida a equação por d. Como d\mid a e d\mid b, definimos inteiros
a'=\frac{a}{d},\qquad b'=\frac{b}{d}.
Pelo fato de d ser \gcd(a,b) conclui-se que \gcd(a',b')=1. Agora a equação original fica
a' x + b' y = 1.
Qualquer divisor comum g de x e y divide o lado esquerdo, logo divide 1. Portanto g=\pm 1. Assim o único divisor comum é 1 (em valor absoluto), o que significa \gcd(x,y)=1.
Exemplo ilustrativo: se a=6, b=10, então d=2 e a'=3, b'=5. Se x=2, y=-1 temos 3\cdot 2 + 5\cdot (-1)=1 e evidentemente \gcd(2,-1)=1.

Passo 6

Conclusões finais, orientação de uso para prova:
  • Para mostrar que uma equação linear a x + b y = c tem solução inteira, primeiro calcule d=\gcd(a,b). Se d\nmid c a prova é curta: não existe solução. Se d\mid c, use o algoritmo estendido de Euclides (ou o argumento do menor elemento positivo apresentado) para obter s,t tais que a s + b t = d e então multiplique por k=c/d para obter a solução procurada.
  • Se conseguir representar d=\gcd(a,b) como combinação linear a x + b y, então automaticamente os coeficientes x,y são coprimos, por causa da divisão por d que reduz a combinação a uma que dá 1.
Força aí — essa é uma das ferramentas mais úteis em teoria dos números: sempre teste se o \gcd divide o lado direito e, se dividir, use Bézout (algoritmo estendido) para construir a solução.

Resposta

(a) Existem inteiros x,y tais que c=a x+b y se, e somente se, \gcd(a,b)\mid c.
(b) Se existem inteiros x,y tais que a x+b y=\gcd(a,b), então \gcd(x,y)=1.

Exercícios relacionados