Sejam
inteiros relativamente primos e seja
um inteiro arbitrário… Prove que
(
se, e somente se,
e
. Mostrar com um exemplo que a hipótese
é essencial.
Passo 1
O enunciado dá:
são inteiros com
e
é um inteiro qualquer. Pede-se para provar a equivalência:
Vou entender e usar a interpretação padrão de congruência:
significa que
divide
(ou seja, existe inteiro
tal que
). Não resolvo nada ainda; apenas registrei o que é dado e o que é pedido.
Passo 2
Provo a implicação direta: se
então
e
.
Explicação e conta:
significa que existe inteiro
com
Como
divide o produto
, segue que
, ou seja
. De modo análogo,
, portanto
. Isso usa apenas a propriedade básica: se
divide
e
divide
, então
divide
; aqui basta ver que
divide
.
Passo 3
Agora prove a implicação recíproca usando que
: se
e
então
.
Primeiro reescrevo as hipóteses em forma de divisibilidade: existem inteiros
e
tais que
A partir de
obtemos que
divide
, isto é
. Para concluir que
preciso mostrar que, apesar de
dividir o produto
, ele divide já o fator
— e aí entra a hipótese
.
Passo 4
Apresento e provo um lema útil (muito usado em provas de teoria dos números):
Lema. Se inteiros
satisfazem
e
, então
.
Prova do lema (passo a passo, usando identidade de Bézout): como
, o Teorema de Bézout garante que existem inteiros
tais que
Multiplico essa identidade por
:
Pelo enunciado do lema
, então
divide
; e claramente
divide
. Assim
divide a soma
, que é igual a
. Logo
. Isso prova o lema.
Passo 5
Aplico o lema à nossa situação: tomemos
,
e
(onde
como em Passo 3). Temos
e
, então pelo lema segue que
. Assim existe inteiro
tal que
. Substituindo em
dá
logo
, isto é
. Isso completa a prova da implicação recíproca.
Passo 6
Conclusão final da prova: com os Passos 2 e 5 mostrei as duas implicações, portanto, quando
,
Agora apresento um exemplo que mostra que a hipótese
é essencial (ou seja, sem ela a afirmação pode falhar).
Exemplo (contraexemplo quando não são primos entre si): escolha
,
(aqui
). Tome
. Calculamos:
porque
e
. Porém
não divide
, logo
Portanto a equivalência falha se
; a hipótese é realmente necessária.