(Primos de Fermat). O
-ésimo número de Fermat é
; um primo de Fermat é um número de Fermat que é primo.
Neste exercício você verá porque é necessário tomar expoentes que são potências de 2 .
(a) Mostre que se
com
e
ímpar, e
é inteiro então o número (
) é composto.
(b) Conforme o exercício 7 , todo número inteiro positivo
se escreve de modo único como
ou
com
ímpar,
.
Conclua que se
é primo então
é uma potência de 2 , ou seja,
é um primo de Fermat. Os únicos primos de Fermat conhecidos são
\footnotetext{
O Teorema de Gauss-Wantzel sobre polígonos construtíveis diz que é possível construir um polígono regular de
lados apenas com régua e compasso se e somente se
em que
e
são primos de Fermat distintos.
(a) Mostre que se
(b) Conforme o exercício 7 , todo número inteiro positivo
Conclua que se
Passo 1
O enunciado pede duas coisas claras:
(a) Provar que, se com
e
ímpar, e
inteiro, então
é composto.
(b) Usando que todo inteiro positivo se escreve de modo único como
ou
com
ímpar, concluir que se
é primo então
é potência de
.
(a) Provar que, se
(b) Usando que todo inteiro positivo
Informações dadas que vamos usar:
- Em (a):
com , ímpar, e inteiro. - Em (b): a unicidade da escrita
ou com ímpar .
Agora vamos provar passo a passo.
Passo 2
Vamos apresentar e provar uma identidade algébrica útil (é o truque principal). Seja
um número e
um inteiro ímpar
. A identidade é
Vou mostrar por multiplicação que isso funciona: multiplica-se
pela soma alternada
. Ao multiplicar,
Reindexando e agrupando termos percebe-se que todos os termos com potências intermédias de
se cancelam por causa dos sinais alternados (isto é a essência: termos
aparecem com coeficientes que se anulam), sobrando apenas
do primeiro somatório e
do segundo. Assim o produto dá exatamente
. (Verficação direta com
:
.
Essa identidade vale só quando
é ímpar; se
fosse par a fatoração com
não seria verdadeira.
Passo 3
Agora aplico a identidade ao nosso problema em (a). Tome
Como
temos
Pela identidade do Passo 2 (porque
é ímpar), obtemos a fatoração
Passo 4
Precisamos verificar que os dois fatores acima são inteiros maiores que
, o que garante que
é composto. Primeiro,
. Como
e
temos
, logo
. Portanto
. Segundo, o outro fator é um inteiro positivo porque é soma e subtração de potências de
com resultado positivo (alternância de sinais mas com termo dominante
e termo constante
); de modo mais simples, note que
e como
(pois
e
), a razão é um inteiro maior que
. Assim ambos os fatores são
, então
tem uma fatoração não-trivial e é composto. Isso prova (a).
Passo 5
Passo para (b). Pelo enunciado (ou exercício anterior) qualquer inteiro
tem representação única: ou
(potência de
) ou
com
e
ímpar. Suponha agora que
é primo. Se
não fosse potência de
, então estaria na forma
com
e
ímpar; mas aplicando (a) com
obteríamos que
é composto, contradição. Portanto não pode ocorrer esse caso: deve ser
para algum
. Em outras palavras, se
é primo então
é potência de
. Esses primos são exatamente os primos de Fermat.
Passo 6
Resumo final (e um exemplo para fixar): a razão pela qual só devemos testar
potências de
ao procurar primos da forma
é que sempre que
tiver um fator ímpar
a soma
se fatoriza não-trivialmente (pela identidade do Passo 2 aplicada a
). Exemplo concreto: com
,
,
(logo
) temos
, claramente composto.
Resposta
(a)
é composto; de fato, com
e
ímpar
,
com ambos os fatores inteiros
.
(b) Se é primo então
é potência de
; isto é, primos da forma
só podem ocorrer quando
(são os primos de Fermat).
(b) Se