Prove que um inteiro n>1 é primo se, e somente se, (n-2)!equiv 1 (bmod n).

Passo 1

O enunciado pede para mostrar a equivalência
n>1 é primo Long<=ftrightarrow (n-2)!equiv1pmod n é
O conteúdo central é aritmética modular e análise de fatores em (n-2)!. Vamos mostrar as duas implicações:
1. Se n é primo então (n-2)!equiv1pmod n.
2. Se (n-2)!equiv1pmod n então n é primo.

Passo 2

( Rightarrow) Suponha que n é primo. Então no corpo Zn cada elemento ain1,2,dots,n-1 tem inverso único a^-1, e as únicas soluções de
a^2equiv1pmod n
são aequiv1 e aequiv n-1.
Em particular, entre os números 1,2,dots,n-2 1 é auto-inverso. Portanto podemos agrupar cada ain2,dots,n-2 com seu inverso distinto a^-1, e cada par contribui com acdot a^-1equiv1. Ficamos então com
(n-2)! =1;times;proda=2^n-2a equiv1;times;prodsubstackpares (a,a^-1)1 equiv1pmod n

Passo 3

( Leftarrow) Suponha agora que (n-2)!equiv1pmod n. Vamos mostrar que n não pode ser composto.
— Se n=4, então (4-2)!=2notequiv1pmod4, logo não satisfaz a condição.
— Se n é composto e n>4, existe divisor próprio d com 1<d<n-1. Então também m=n/d satisfaz 1<m<n-1. Ambos d e m aparecem em (n-2)!, de modo que
dcdot m = n | (n-2)!,
implicando (n-2)!equiv0pmod nneq1.
Assim nenhum n composto pode satisfazer (n-2)!equiv1pmod n, e segue que se (n-2)!equiv1pmod n então n é primo.

Resposta

Portanto, mostramos as duas direções e concluímos que
n>1 é primo Long<=ftrightarrow (n-2)!equiv1pmod n é

Exercícios de Livros Relacionados