Seja n inteiro positivo, n>4.
(a) Mostre que se n \mid(n-1) ! então n é composto.
(sugestão: suponha, por contradição, que n é primo)
(b) Reciprocamente, mostre que se n é composto então n \mid(n-1) !.
(sugestão: você pode começar por " n=a b com 1<a<n, 1<b<n ". Se a \neq b então o resultado segue da definição do fatorial de n-1. Use o Teorema Fundamental da Aritmética para provar que o único caso em que não é possível obter a \neq b é quando n=p^{2} com p primo, e resolva este caso separadamente.)

Passo 1

Enunciado e dados importantes (o que se pede).
O enunciado considera um inteiro positivo (n) com (n>4) e pede duas coisas:
(a) Mostrar que: se \,n \mid (n-1)! então n é composto.
(b) Mostrar o recíproco: se n é composto então \,n \mid (n-1)!.
Informações relevantes dadas/implícitas:
  • (n) é inteiro positivo e (n>4).
  • A notação (n-1)! é o fatorial de (n-1), ou seja o produto (n-1)! = 1\cdot 2\cdot 3\cdots (n-1).
  • A relação (n \mid (n-1)!) significa que (n-1)! é múltiplo de (n), isto é existe inteiro k tal que (n-1)! = k n.
Perguntas claras:
  • (a) Provar que, sob a hipótese (n \mid (n-1)!), (n) não pode ser primo (logo é composto).
  • (b) Provar que se (n) é composto então de fato (n \mid (n-1)!).
A partir daqui começamos a resolver passo a passo.

Passo 2

Parte (a): estratégia por contradição — suponha que n seja primo e mostre que isso contradiz n\mid (n-1)!.
Vou assumir que n é primo (digamos n=p) e explicar porque, para um primo p, não é possível ter p\mid (p-1)!. A ferramenta que vou usar é o teorema de Wilson (vou prová-lo de maneira elementar): para p primo vale
(p-1)! \equiv -1 \pmod p,
ou seja (p-1)! deixa resto -1 ao ser dividido por p, portanto p não divide (p-1)!.

Passo 3

Explicação e prova elementar do Teorema de Wilson (por que (p-1)! \equiv -1\pmod p quando p é primo).
Conceitos que uso e explico:
  • Em aritmética modular, dizer que um número a tem inverso multiplicativo módulo p significa que existe b tal que ab\equiv 1\pmod p.
  • Quando p é primo, todo a com 1\le a\le p-1 tem inverso módulo p porque \gcd(a,p)=1.
    Prova por pareamento:
  1. Para cada a\in\{2,3,\dots,p-2\} existe um inverso a^{-1} distinto de a (exceto nos casos em que a\equiv a^{-1}, que resolveremos abaixo). Então podemos agrupar os elementos de \{2,\dots,p-2\} em pares (a,a^{-1}) cuja multiplicação é congruente a 1 módulo p.
  2. Quais a satisfazem a\equiv a^{-1}\pmod p? Isso é equivalente a a^2\equiv 1\pmod p, i.e. (a-1)(a+1)\equiv 0\pmod p. Como p é primo, isso ocorre só se a\equiv 1 ou a\equiv -1 (ou seja a=1 ou a=p-1).
  3. Assim o produto de todos os 1,2,\dots,p-1 pode ser escrito como
(p-1)! \equiv 1\cdot (p-1)\cdot \prod_{\text{pares }(a,a^{-1})} a\cdot a^{-1} \equiv 1\cdot (p-1)\cdot 1 \equiv -1 \pmod p,
porque p-1\equiv -1\pmod p.
Conclusão: para todo primo p vale (p-1)!\equiv -1\pmod p, logo (p-1)! não é múltiplo de p. Isso contradiz a hipótese n\mid (n-1)! caso n fosse primo.

Passo 4

Concluir (a) com a contradição.
Resumo do raciocínio: assumimos n\mid (n-1)! e supusemos n primo; pelo argumento acima (Wilson) para um primo p temos (p-1)!\not\equiv 0\pmod p, ou seja p\nmid (p-1)!. Isso contraria a hipótese. Portanto n não pode ser primo — ou seja, n é composto. Assim a parte (a) está provada.

Passo 5

Parte (b): mostrar que se n é composto então n\mid (n-1)!.
Estratégia geral e ideia intuitiva: se n é composto então existe um divisor não-trivial a com 1<a<n; escrevemos n=ab com 1<a\le b<n. Se a\neq b então tanto a quanto b aparecem como fatores em (n-1)! (pois são \le n-1) e, portanto, ab=n divide (n-1)!. Resta tratar o caso em que a única possibilidade é a=b (i.e. n é um quadrado perfeito de um número). Vou mostrar que, nesse caso, necessariamente n=p^{2} com p primo, e então provar que p^{2} divide (p^{2}-1)! sempre que p\ge 3 (o que cobre n>4).

Passo 6

Escolhendo o menor divisor a>1 e deduzindo que é primo; análise do caso a<b.
Seja a o menor divisor inteiro de n com a>1. Observações:
  • a é primo: se a fosse composto, teria um divisor d com 1<d<a, o que contradiz a mínima escolha de a.
  • Defina b = n/a. Então 1<b\le n/a e ab=n.
    Agora há duas possibilidades:
    (i) Se a<b então 1<a\le n-1 e 1<b\le n-1; assim ambos a e b aparecem entre os fatores de (n-1)!. Logo (n-1)! contém o fator ab=n e portanto n\mid (n-1)!.
    (ii) Se a=b então n=a^{2}. Vamos estudar esse caso com mais cuidado.

Passo 7

Mostrar que se a=b então a é primo e n=p^{2}; tratar n=p^{2} com p\ge 3.
Se a=b então n=a^{2} e, como vimos, a é primo (porque a era o menor divisor >1). Portanto n=p^{2} para algum primo p. Como o enunciado exige n>4, esse caso com p=2 (que daria n=4) está excluído; logo p\ge 3.
Agora precisamos mostrar que para todo primo p\ge 3 vale
p^{2} \mid (p^{2}-1)! .
Duas maneiras de ver isso (vou usar uma conta simples de quantos múltiplos de p existem abaixo de p^{2}).

Passo 8

Contagem de potências de p em (p^{2}-1)! (argumento direto).
O expoente de p em (p^{2}-1)! (denotado v_{p}((p^{2}-1)!)) é pelo menos o número de múltiplos de p entre 1 e p^{2}-1. Os múltiplos são
p,\,2p,\,3p,\dots,(p-1)p,
ou seja há exatamente p-1 múltiplos de p estritamente menores que p^{2}. Cada um desses múltiplos contribui pelo menos com um fator p ao fatorial, portanto
v_{p}((p^{2}-1)!) \ge p-1.
Como p\ge 3 (pois n>4), temos p-1\ge 2. Portanto v_{p}((p^{2}-1)!)\ge 2, o que implica p^{2}\mid (p^{2}-1)!. Assim o caso n=p^{2} com p\ge 3 também está resolvido.
(Observação opcional e econômica: usando a fórmula de Legendre dá-se exatamente v_{p}((p^{2}-1)!)=\left\lfloor\frac{p^{2}-1}{p}\right\rfloor+\left\lfloor\frac{p^{2}-1}{p^{2}}\right\rfloor+\cdots = (p-1)+0+\cdots = p-1\ge 2.)

Passo 9

Conclusão da parte (b).
Juntando os casos: se n é composto então existe um divisor a com 1<a\le b<n tal que n=ab. Se a<b então a e b aparecem em (n-1)! e n\mid (n-1)!. Se a=b então n=p^{2} com p\ge 3 e mostramos que também p^{2}\mid (p^{2}-1)!. Logo em todos os casos n\mid (n-1)!. Isso prova o recíproco pedido.

Resposta

(a) n é composto.
(b) Se n é composto então n \mid (n-1)!.

Exercícios relacionados