S-3.26 Mostre que se é composto, então divide o produto
Passo 1
O enunciado pede para mostrar que, sempre que é composto, então
ou seja, que
(n-1)!equiv0pmod n
O que vamos usar é o fato de que todo número composto tem fatoração em primos e a fórmula de Legendre para contar, em (n-1)!, quantas vezes cada primo aparece.
Passo 2
Seja
n = p1^a1p2^a2cdots pr^ar
a fatoração de n em primos, com r>=1 e pelo menos um ai>=1.
Para cada primo pi vamos comparar o seu expoente em n (que é ai) com o seu expoente em (n-1)!. Pelas contas de Legendre, o expoente de pi em (n-1)! é
nupil((n-1)!r) =sumk=1^inftyllfloorn-1pi^krrfloor
Basta mostrar que, para cada i,
nupil((n-1)!r);>=;ai
Passo 3
Fixemos um primo divisor p=pi de n, com multiplicidade a=ai. Como n é composto, n>=4. Vamos ver que sempre que (p,a)neq(2,2)—isto é, sempre que nneq4—a soma
É fácil checar que, para todo par (p,a)neq(2,2) com a>=2, vale
p^a-1+p^a-2-2;>=;a
Para a=1 já vimos que o primeiro termo basta (lfloor(n-1)/prfloor>=1).
A única falha ocorre em p=2,a=2, isto é, em n=2^2=4. De fato, nu2(3!)=lfloor3/2rfloor=1<2, e por isso 4nmid3!.
Mas para qualquer outro composto nneq4 a condição nupi((n-1)!)>= ai vale para todo primo pi de n.
Passo 4
Como cada primo pi aparece em (n-1)! com multiplicidade pelo menos ai, concluímos que
n = prodi=1^r pi^ai ;m|; (n-1)!
Passo 5
Logo, para todo n composto diferente de 4 temos
(n-1)!equiv0pmod n
O único composto para o qual isso falha é n=4, pois 3!=6 e 6notequiv0pmod4.