Sejam
inteiros e
um inteiro não nulo. Provar que
se, e somente se,
,
Passo 1
O enunciado pede para provar uma equivalência entre duas congruências. Dados:
e
A afirmação a provar é:
A afirmação a provar é:
Informações relevantes dadas pelo enunciado:
são inteiros quaisquer;
é inteiro não nulo.
Não há outras hipóteses (por exemplo, pode ser zero também). A tarefa é mostrar as duas implicações da equivalência: a)
e b)
.
Não há outras hipóteses (por exemplo,
Passo 2
Lembrando a definição que vamos usar várias vezes:
Dizemos quando
divide
. Ou seja,
Dizemos
o que significa que existe um inteiro
tal que
Também vamos usar a ideia simples de cancelamento em
: se
e
com
, então
. Uma forma de ver isso é subtrair e fatorar:
; como
e
não tem divisores de zero, segue
.
Passo 3
Prova da implicação direta:
Começamos assumindo
. Pela definição de congruência existe
tal que
Multiplicando ambos os lados por
obtemos
A última igualdade mostra que
divide
, ou seja,
Pela definição de congruência, isso é precisamente
Assim a primeira implicação está provada. (Comentário prático: aqui só multiplicamos uma igualdade inteira por
— operação válida mesmo que
.)
Passo 4
Prova da implicação inversa:
Assumimos agora
. Pela definição, existe
tal que
Reescrevemos essa igualdade fatorando
:
Como no enunciado temos
, podemos aplicar o argumento de cancelamento: a igualdade acima implica que
ou seja
Isso mostra que
divide
, portanto, pela definição,
Observação sobre o caso
: se
então
e a condição
é
, o que força
; como
segue
, ou seja
, que é exatamente
. A prova acima já cobre esse caso graças ao cancelamento por
.
Passo 5
Conclusão: mostramos ambas as implicações, logo as duas afirmações são equivalentes: