(Primos de Fermat). O k-ésimo número de Fermat é \mathrm{f}_{k}=2^{2^{k}}+1; um primo de Fermat é um número de Fermat que é primo. { }^{1} Neste exercício você verá porque é necessário tomar expoentes que são potências de 2 .
(a) Mostre que se n=2^{k} m com k \geq 1 e m \geq 3, m ímpar, e a>1 é inteiro então o número ( a^{n}+1 ) é composto.
(b) Conforme o exercício 7 , todo número inteiro positivo n se escreve de modo único como n=2^{k} ou n=2^{k} m com m \geq 3 ímpar, k \geq 0.
Conclua que se 2^{n}+1 é primo então n é uma potência de 2 , ou seja, 2^{n}+1 é um primo de Fermat. Os únicos primos de Fermat conhecidos são
2^{1}+1=3, \quad 2^{2}+1=5, \quad 2^{4}+1=17, \quad 2^{8}+1=257, \quad 2^{16}+1=65.537 .
\footnotetext{
{ }^{1} O Teorema de Gauss-Wantzel sobre polígonos construtíveis diz que é possível construir um polígono regular de n lados apenas com régua e compasso se e somente se n=2^{m} p_{1} p_{2} \cdots p_{k} em que m \geq 0 e p_{1}, p_{2}, \ldots são primos de Fermat distintos.

Passo 1

O enunciado pede duas coisas claras:
(a) Provar que, se n=2^{k}m com k\ge 1 e m\ge 3 ímpar, e a>1 inteiro, então a^{n}+1 é composto.
(b) Usando que todo inteiro positivo n se escreve de modo único como n=2^{k} ou n=2^{k}m com m\ge 3 ímpar, concluir que se 2^{n}+1 é primo então n é potência de 2.
Informações dadas que vamos usar:
  • Em (a): n=2^{k}m com k\ge1, m\ge3 ímpar, e a>1 inteiro.
  • Em (b): a unicidade da escrita n=2^{k} ou n=2^{k}m com m ímpar \ge3.
Agora vamos provar passo a passo.

Passo 2

Vamos apresentar e provar uma identidade algébrica útil (é o truque principal). Seja x um número e m um inteiro ímpar \ge 3. A identidade é
x^{m}+1=(x+1)\bigl(x^{m-1}-x^{m-2}+x^{m-3}-\cdots -x+1\bigr).
Vou mostrar por multiplicação que isso funciona: multiplica-se (x+1) pela soma alternada \sum_{j=0}^{m-1}(-1)^{j}x^{m-1-j}. Ao multiplicar,
(x+1)\sum_{j=0}^{m-1}(-1)^{j}x^{m-1-j} = \sum_{j=0}^{m-1}(-1)^{j}x^{m-j} + \sum_{j=0}^{m-1}(-1)^{j}x^{m-1-j}.
Reindexando e agrupando termos percebe-se que todos os termos com potências intermédias de x se cancelam por causa dos sinais alternados (isto é a essência: termos x^{m-1},x^{m-2},\dots,x aparecem com coeficientes que se anulam), sobrando apenas x^{m} do primeiro somatório e +1 do segundo. Assim o produto dá exatamente x^{m}+1. (Verficação direta com m=3: x^{3}+1=(x+1)(x^{2}-x+1).
Essa identidade vale só quando m é ímpar; se m fosse par a fatoração com (x+1) não seria verdadeira.

Passo 3

Agora aplico a identidade ao nosso problema em (a). Tome
x:=a^{2^{k}}.
Como n=2^{k}m temos
a^{n}+1 = a^{2^{k}m}+1 = \bigl(a^{2^{k}}\bigr)^{m}+1 = x^{m}+1.
Pela identidade do Passo 2 (porque m é ímpar), obtemos a fatoração
a^{n}+1 = (x+1)\bigl(x^{m-1}-x^{m-2}+\cdots -x+1\bigr).

Passo 4

Precisamos verificar que os dois fatores acima são inteiros maiores que 1, o que garante que a^{n}+1 é composto. Primeiro, x=a^{2^{k}}. Como a>1 e k\ge 1 temos 2^{k}\ge 2, logo x=a^{2^{k}}\ge a^{2}>1. Portanto x+1>1. Segundo, o outro fator é um inteiro positivo porque é soma e subtração de potências de x com resultado positivo (alternância de sinais mas com termo dominante x^{m-1} e termo constante +1); de modo mais simples, note que
\text{segundo fator}=\frac{x^{m}+1}{x+1},
e como x^{m}+1>x+1 (pois m\ge3 e x>1), a razão é um inteiro maior que 1. Assim ambos os fatores são \ge 2, então a^{n}+1 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 n tem representação única: ou n=2^{k} (potência de 2) ou n=2^{k}m com k\ge0 e m\ge3 ímpar. Suponha agora que 2^{n}+1 é primo. Se n não fosse potência de 2, então estaria na forma n=2^{k}m com k\ge1 e m\ge3 ímpar; mas aplicando (a) com a=2 obteríamos que 2^{n}+1 é composto, contradição. Portanto não pode ocorrer esse caso: deve ser n=2^{k} para algum k. Em outras palavras, se 2^{n}+1 é primo então n é potência de 2. 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 n potências de 2 ao procurar primos da forma 2^{n}+1 é que sempre que n tiver um fator ímpar m\ge3 a soma 2^{n}+1 se fatoriza não-trivialmente (pela identidade do Passo 2 aplicada a x=2^{2^{k}}). Exemplo concreto: com a=3, k=1, m=3 (logo n=6) temos 3^{6}+1=(3^{2})^{3}+1=9^{3}+1=(9+1)(9^{2}-9+1)=10\cdot 73=730, claramente composto.

Resposta

(a) a^{n}+1 é composto; de fato, com x=a^{2^{k}} e m ímpar \ge3,
a^{n}+1=x^{m}+1=(x+1)\bigl(x^{m-1}-x^{m-2}+\cdots -x+1\bigr),
com ambos os fatores inteiros >1.
(b) Se 2^{n}+1 é primo então n é potência de 2; isto é, primos da forma 2^{n}+1 só podem ocorrer quando n=2^{k} (são os primos de Fermat).

Exercícios relacionados