Sejam
e
inteiros. Provar que:
(a) existem inteiros
e
tais que
se, e somente se, o
.
(b) se existem inteiros
e
tais que
, então o
.
(a) existem inteiros
(b) se existem inteiros
Passo 1
O enunciado dá que
,
e
são inteiros e pede que mostremos duas coisas:
(a) Mostrar que existem inteiros
e
tais que
se, e somente se,
.
(b) Mostrar que, se existem inteiros
e
tais que
, então
.
Informações relevantes fornecidas:
-
. - A função
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
Por definição de máximo divisor comum, temos que
é um divisor comum de
e
(isto é,
e
) e qualquer outro divisor comum de
e
divide
. Uma propriedade imediata e muito usada: se
e
então
divide qualquer combinação linear
para inteiros
. Vou usar essa propriedade para provar uma das direções da parte (a).
Prova da implicação direta de (a): se existem inteiros
tais que
, então
.
Raciocínio: como
e
, qualquer combinação linear
é múltiplo de
. Assim, se
então
. Exemplo concreto para ver a ideia: se
,
,
, então qualquer
é múltiplo de
.
Passo 3
Agora a implicação recíproca de (a): se
então existem inteiros
tais que
.
Estratégia: primeiro provar que existem inteiros
tais que
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
Primeiro,
não é vazio: por exemplo, usando a identidade trivial
ou
, se ao menos um entre
e
for não nulo obtemos um elemento
; se ambos são zeros o enunciado é trivial (caso
tem-se
indefinido, mas normalmente o contexto pressupõe que nem ambos são zero). Como
é um subconjunto dos inteiros positivos e não vazio, ele tem um menor elemento; chame-o de
. Pelo modo como
foi definido, existem inteiros
tais que
Agora provamos que
é divisor comum de
e
. Divida
por
: existem inteiros
e
com
tais que
Reescrevendo
em termos de
:
portanto
é da forma
. Como
e
é o menor número positivo da forma
, a única possibilidade é
. Assim
. Pelo mesmo argumento com
obtemos
. Então
é um divisor comum de
e
.
Como
é o maior divisor comum, temos
. Por outro lado, qualquer divisor comum (em particular
) divide qualquer combinação linear; logo
. Daí
. Juntando as duas desigualdades obtemos
. Em particular existe representação de Bézout:
para certos inteiros
.
Passo 4
Concluir a recíproca de (a) usando a representação de Bézout.
Se
, escreva
com
. Como já provamos que existem
com
, basta multiplicar essa igualdade por
:
Portanto
e
são inteiros que satisfazem
. Isso mostra que a condição
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
, então multiplicando-a obtém-se qualquer múltiplo do
.
Passo 5
Prova de (b). Queremos mostrar: se existem inteiros
tais que
com
, então
.
Argumento direto simples e elegante: divida a equação por
. Como
e
, definimos inteiros
Pelo fato de
ser
conclui-se que
. Agora a equação original fica
Qualquer divisor comum
de
e
divide o lado esquerdo, logo divide
. Portanto
. Assim o único divisor comum é
(em valor absoluto), o que significa
.
Exemplo ilustrativo: se
,
, então
e
,
. Se
,
temos
e evidentemente
.
Passo 6
Conclusões finais, orientação de uso para prova:
-
Para mostrar que uma equação linear
tem solução inteira, primeiro calcule . Se a prova é curta: não existe solução. Se , use o algoritmo estendido de Euclides (ou o argumento do menor elemento positivo apresentado) para obter tais que e então multiplique por para obter a solução procurada. -
Se conseguir representar
como combinação linear , então automaticamente os coeficientes são coprimos, por causa da divisão por que reduz a combinação a uma que dá .
Força aí — essa é uma das ferramentas mais úteis em teoria dos números: sempre teste se o
divide o lado direito e, se dividir, use Bézout (algoritmo estendido) para construir a solução.
Resposta
(a) Existem inteiros
tais que
se, e somente se,
.
(b) Se existem inteiros tais que
, então
.
(b) Se existem inteiros