Seja
um inteiro,
. Mostre que se para quaisquer inteiros
,
então
é primo.
Passo 1
O enunciado dá que
é um inteiro com
e que a seguinte propriedade vale para quaisquer inteiros
:
A tarefa é mostrar que
é primo.
Informações relevantes: é inteiro e diferente de
; a propriedade de divisibilidade acima vale para todos os inteiros
. O que se pede: provar que
é primo (ou seja, que não é composto).
Informações relevantes:
Passo 2
Vamos lembrar e explicar cuidadosamente o que significam as palavras que vamos usar.
Definição de divisibilidade: dizer que
divide
(escrevemos
) significa que existe um inteiro
tal que
Isto nos dá uma consequência útil: se
então
, e portanto, se
temos
.
Definição de primo e composto: um inteiro
com
é primo se seus únicos divisores inteiros são
e
. Se
e existe um divisor inteiro
com
, dizemos que
é composto (ou não-primo). Observação: o enunciado já excluiu
, então a única alternativa a “primo” é ser composto.
Passo 3
Estratégia do argumento (explicada como um amigo que te guia): vou provar a afirmação usando o contrarrecíproco (contraposição). Ou seja, vou provar que se
não for primo (isto é, se
for composto), então a propriedade dada falha. Isso é suficiente porque a negação do enunciado “se P então Q” é “se não Q então não P”; então mostrar que composto implica falha da propriedade dá que, se a propriedade é verdadeira,
não pode ser composto — portanto é primo.
Passo 4
Suponha que
não seja primo. Como
, isso significa que
é composto: existe uma fatoração não-trivial de
. Ou seja, existem inteiros positivos
e
tais que
e
(Estou escolhendo
divisores de
.)
Passo 5
Agora vou construir um contraexemplo à propriedade dada usando
e
. Calculemos
:
Mostremos que
. Se
então
e
, logo
. Se
então
e
, então
também (porque
). Em resumo, em ambos os casos temos
.
Passo 6
Mostremos que simultaneamente
e
. Suponha, para obter contradição, que
. Então existe inteiro
tal que
. Tomando valores absolutos:
Se
então
, mas por construção
satisfaz
, então
. Logo
e assim
. Mas isto contradiz a escolha de
com
. Portanto não pode acontecer
. A mesma argumentação (trocando
por
) mostra que
.
Passo 7
Concluímos que, no caso em que
é composto, existem inteiros
(escolhidos como os fatores não-triviais
de
) tais que
mas nem
nem
. Logo a propriedade dada falha.
Passo 8
Pelo argumento por contraposição: se a propriedade dada vale para todos os inteiros
, então não pode ocorrer o caso "
é composto". Como já excluímos
, segue que
deve ser primo. (Isto fecha a prova.)