Seja
inteiro positivo,
.
(a) Mostre que se
! então
é composto.
(sugestão: suponha, por contradição, que n é primo)
(b) Reciprocamente, mostre que se
é composto então
!.
(sugestão: você pode começar por "
com
". Se
então o resultado segue da definição do fatorial de
. Use o Teorema Fundamental da Aritmética para provar que o único caso em que não é possível obter
é quando
com
primo, e resolva este caso separadamente.)
(a) Mostre que se
(sugestão: suponha, por contradição, que n é primo)
(b) Reciprocamente, mostre que se
(sugestão: você pode começar por "
Passo 1
Enunciado e dados importantes (o que se pede).
O enunciado considera um inteiro positivo com
e pede duas coisas:
O enunciado considera um inteiro positivo
(a) Mostrar que: se
então
é composto.
(b) Mostrar o recíproco: se é composto então
.
(b) Mostrar o recíproco: se
Informações relevantes dadas/implícitas:
-
é inteiro positivo e . - A notação
é o fatorial de , ou seja o produto . - A relação
significa que é múltiplo de , isto é existe inteiro tal que .
Perguntas claras:
- (a) Provar que, sob a hipótese
, não pode ser primo (logo é composto). - (b) Provar que se
é composto então de fato .
A partir daqui começamos a resolver passo a passo.
Passo 2
Parte (a): estratégia por contradição — suponha que
seja primo e mostre que isso contradiz
.
Vou assumir que é primo (digamos
) e explicar porque, para um primo
, não é possível ter
. A ferramenta que vou usar é o teorema de Wilson (vou prová-lo de maneira elementar): para
primo vale
Vou assumir que
ou seja
deixa resto
ao ser dividido por
, portanto
não divide
.
Passo 3
Explicação e prova elementar do Teorema de Wilson (por que
quando
é primo).
Conceitos que uso e explico:
Conceitos que uso e explico:
- Em aritmética modular, dizer que um número
tem inverso multiplicativo módulo significa que existe tal que . - Quando
é primo, todo com tem inverso módulo porque .
Prova por pareamento:
- Para cada
existe um inverso distinto de (exceto nos casos em que , que resolveremos abaixo). Então podemos agrupar os elementos de em pares cuja multiplicação é congruente a módulo . - Quais
satisfazem ? Isso é equivalente a , i.e. . Como é primo, isso ocorre só se ou (ou seja ou ). - Assim o produto de todos os
pode ser escrito como
porque
.
Conclusão: para todo primo vale
, logo
não é múltiplo de
. Isso contradiz a hipótese
caso
fosse primo.
Conclusão: para todo primo
Passo 4
Concluir (a) com a contradição.
Resumo do raciocínio: assumimos e supusemos
primo; pelo argumento acima (Wilson) para um primo
temos
, ou seja
. Isso contraria a hipótese. Portanto
não pode ser primo — ou seja,
é composto. Assim a parte (a) está provada.
Resumo do raciocínio: assumimos
Passo 5
Parte (b): mostrar que se
é composto então
.
Estratégia geral e ideia intuitiva: se é composto então existe um divisor não-trivial
com
; escrevemos
com
. Se
então tanto
quanto
aparecem como fatores em
(pois são
) e, portanto,
divide
. Resta tratar o caso em que a única possibilidade é
(i.e.
é um quadrado perfeito de um número). Vou mostrar que, nesse caso, necessariamente
com
primo, e então provar que
divide
sempre que
(o que cobre
).
Estratégia geral e ideia intuitiva: se
Passo 6
Escolhendo o menor divisor
e deduzindo que é primo; análise do caso
.
Seja o menor divisor inteiro de
com
. Observações:
Seja
-
é primo: se fosse composto, teria um divisor com , o que contradiz a mínima escolha de . - Defina
. Então e .
Agora há duas possibilidades:
(i) Seentão e ; assim ambos e aparecem entre os fatores de . Logo contém o fator e portanto .
(ii) Seentão . Vamos estudar esse caso com mais cuidado.
Passo 7
Mostrar que se
então
é primo e
; tratar
com
.
Se então
e, como vimos,
é primo (porque
era o menor divisor >1). Portanto
para algum primo
. Como o enunciado exige
, esse caso com
(que daria
) está excluído; logo
.
Se
Agora precisamos mostrar que para todo primo
vale
Duas maneiras de ver isso (vou usar uma conta simples de quantos múltiplos de
existem abaixo de
).
Passo 8
Contagem de potências de
em
(argumento direto).
O expoente de em
(denotado
) é pelo menos o número de múltiplos de
entre
e
. Os múltiplos são
O expoente de
ou seja há exatamente
múltiplos de
estritamente menores que
. Cada um desses múltiplos contribui pelo menos com um fator
ao fatorial, portanto
Como
(pois
), temos
. Portanto
, o que implica
. Assim o caso
com
também está resolvido.
(Observação opcional e econômica: usando a fórmula de Legendre dá-se exatamente
.)
Passo 9
Conclusão da parte (b).
Juntando os casos: se é composto então existe um divisor
com
tal que
. Se
então
e
aparecem em
e
. Se
então
com
e mostramos que também
. Logo em todos os casos
. Isso prova o recíproco pedido.
Juntando os casos: se
Resposta
(a)
é composto.
(b) Se é composto então
.
(b) Se