S-3.26 Mostre que se é composto, então divide o produto

Passo 1

O enunciado pede para mostrar que, sempre que n é composto, então
n ;m|;1times2times3timescdotstimes(n-1),,
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
sumk>=1llfloorn-1p^krrfloor
ultrapassa a.
  1. Primeiro termo ( k=1):
    llfloorn-1prrfloor =llfloorp^acdot(cdots)-1prrfloor =p^,a-1cdot(cdots);-;1,
    onde “ cdots” é um inteiro >=1.
    • Se a>=2 então llfloorn-1prrfloor>= p^a-1-1.
    • Se a=1 então llfloorn-1prrfloor>=1.
  2. Segundo termo ( k=2):
    llfloorn-1p^2rrfloor ;=; p^,a-2cdot(cdots);-;1 (se a>=2),
    e zero se a=1.
Somando, para a>=2,
nupl((n-1)!r) ;>=; l(p^a-1-1r);+;l(p^a-2-1r) ;=; p^a-1+p^a-2-2
É 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.

Resposta

Para todo número composto nneq4 vale
nmid1cdot2cdotcdotscdot(n-1),
isto é, (n-1)!equiv0pmod n.

Exercícios relacionados