Demonstrar as seguintes questões:
Corolário 2: A equação
tem solução se, e somente se,
são inteiros primos entre si.
Corolário 2: A equação
Passo 1
O que o enunciado pede: demonstrar o Corolário 2, que afirma uma equivalência entre duas propriedades. Em palavras claras: precisamos provar que a equação diofantina linear
tem solução em inteiros
e
se, e somente se,
e
são inteiros primos entre si (ou seja,
).
Informações dadas (assumidas do enunciado):
e
são inteiros; queremos soluções
também inteiros. O objetivo é provar duas implicações:
- Se existem inteiros
tais que então . - Se
então existem inteiros tais que .
Passo 2
Definições e conceitos básicos que vamos usar (explicados devagar):
- Dizemos que um inteiro
divide um inteiro (escrevemos ) quando existe inteiro com . Ex.: porque . - O máximo divisor comum de
e , escrito , é o maior inteiro positivo que divide simultaneamente e . - Se um inteiro
divide e divide , então dizemos que é um divisor comum. A propriedade chave que usaremos é: se um divisor comum divide uma combinação linear , então divide cada membro dessa combinação (porque se e , então para quaisquer inteiros ).
Vamos também lembrar uma ideia útil (não precisamos aqui provar o algoritmo completo): o método clássico para mostrar que
pode ser escrito como combinação linear de
e
usa o argumento do “menor elemento positivo” de um conjunto de combinações lineares — esse é o caminho que vou seguir porque é construtivo e elementar.
Passo 3
Prova da implicação fácil (necessidade): se existe solução então
.
Suponha que existam inteiros
tais que
Se
é qualquer divisor comum de
e
, então
divide
e
divide
, logo
divide a soma
. Ou seja,
. Os únicos divisores inteiros de
são
e
, portanto o único divisor positivo comum possível é
. Assim o máximo divisor comum é
. Isso prova que a existência de solução implica que
e
são primos entre si.
Comentário amigável: essa parte é direta — qualquer divisor comum “passa” para a combinação linear e acaba dividindo
, então só pode ser
.
Passo 4
Estratégia para a implicação difícil (suficiência): se
então existe solução. Plano: construir inteiros
com
. Vou usar o argumento do menor elemento positivo do conjunto das combinações lineares de
e
.
Defina o conjunto
Note que
é um subconjunto não vazio dos inteiros positivos (por exemplo, se
então
; se
for negativo podemos escolher
etc.; enfim, existe alguma combinação não nula e podemos considerar valor absoluto se precisar — o que importa é que existem combinações não nulas). Pelo princípio do menor elemento em
,
tem um menor elemento; denote esse menor elemento por
:
Passo 5
Mostrar que
divide
e
divide
.
Pela definição de
, existem inteiros
tais que
Agora use o algoritmo da divisão entre inteiros: divida
por
. Existem inteiros
e
com
tais que
Substituindo
obtemos
Portanto
é uma combinação inteira de
e
. Se
, então
, mas isso contradiz a minimalidade de
pois
. Logo só é possível
. Assim
. Pelo mesmo argumento (dividindo
por
) obtemos
.
Comentário: a ideia é clássica — o resto da divisão de
por
também é combinação linear; se fosse positivo seria menor que
, contradizendo a escolha de
.
Passo 6
Concluir que
e terminar a prova.
Como
divide
e
,
é um divisor comum. Logo
. Por outro lado,
divide qualquer combinação linear de
e
, então
divide
. Como
e
são inteiros positivos e cada um divide o outro, necessariamente
.
Agora use a hipótese
. Então
. Mas lembrando que
foi obtido como combinação linear
, concluímos que existem inteiros
tais que
Isso é exatamente o que queríamos: existência de solução inteira para
.
Comentário simpático: essa parte é a essência do Lema de Bézout — quando duas entradas são primos entre si, 1 aparece como combinação linear delas.
Passo 7
Exemplo prático (para fixar e para você levar pra prova): tome
e
. Aqui
. Aplicando o algoritmo descrito (ou o algoritmo extendido de Euclides) encontra-se, por exemplo,
. De fato,
Então
é solução. Esse tipo de construção é exatamente a aplicação prática do argumento anterior; no exame, se pedirem os coeficientes, você pode executar o algoritmo estendido de Euclides para obtê-los.
Resposta
A equação
tem solução em inteiros
se, e somente se,
.