Mostre que:
é primo.
Resolucão:
Vamos supor n não primo. Então n admite um divisor
, e portanto
. Assim, há pelo menos dois elementos em
não primos com
: ren. Mas isto implica que
é no máximo igual a
. Absurdo.
Passo 1
Resumindo, queremos mostrar que \r
onde
(função totiente de Euler) conta quantos inteiros
em
satisfazem
.
Passo 2
Prova de que
primo
. \r
Se é primo, então todo
com
não admite nenhum divisor comum com
além de 1. Logo \r
para
, \r
enquanto . \r
Isso significa que, dos números , exatamente os
primeiros são coprimos com
. Portanto \r
Se
enquanto
Isso significa que, dos números
Passo 3
Prova de que
é primo. \r
Faremos a contrapartida: se não é primo então
. \r
Como não é primo, existe um divisor próprio
tal que \r
Faremos a contrapartida: se
Como
Então \r
isto é, há pelo menos dois números em
—
e
— que não são coprimos com
. \r
Logo, dentre os inteiros de 1 a
, no máximo
são coprimos com
, ou seja, \r
Logo, dentre os
Isso contradiz
, mostrando que
não pode ser composto, logo deve ser primo.
Resposta
Mostramos que
ocorre exatamente quando
é primo.