# Número de Fermat

Em matemática, um número de Fermat é um número inteiro positivo da forma:
    $F_{n}=2^{2^{n}}+1$
sendo $n$ um número natural.
Pierre de Fermat lançou a conjectura, em uma carta escrita para Marin Mersenne, que estes números eram primos. Mas mais tarde, Leonard Euler provou que não era assim; para $n=5$ , obtinha-se um número composto:
    $F_{5}=2^{2^{5}}+1=2^{32}+1=4294967297=641\cdot 6700417\;$
Até hoje, apenas são conhecidos cinco números primos de Fermat; e não se sabe se há mais ou não:
    $F_{0}=2^{2^{0}}+1=3$
    $F_{1}=2^{2^{1}}+1=5$
    $F_{2}=2^{2^{2}}+1=17$
    $F_{3}=2^{2^{3}}+1=257$
    $F_{4}=2^{2^{4}}+1=65537$
Os números de Fermat de ordem $5$ até $32$, bem como, números enormes como $F_{23288}\,$ e $F_{23471}\,$ são comprovadamente compostos.

## Propriedades dos números de Fermat

* Um número de Fermat é igual ao produto de todos os anteriores mais 2.
Prova por indução: Vale para $F_{1}$, pois $F_{1}=F_{0}+2(5=3+2)$. Agora, se ele vale para $F_{(n-1)}$, então ele vale para $F_{n}$:
* $F_{0}\cdot F_{1}\cdot \ldots \cdot F_{n-2}\cdot F_{n-1}+2=\left(F_{n-1}-2\right)\cdot F_{n-1}+2\,\!$
* $=\left(2^{2^{n-1}}+1-2\right)\cdot \left(2^{2^{n-1}}+1\right)+2\,\!$
* $=\left(2^{2^{n-1}}-1\right)\cdot \left(2^{2^{n-1}}+1\right)+2\,\!$
* $=\left(2^{2^{n-1}}\right)^{2}-1+2=2^{2^{n}}+1=F_{n}\,\!$
* Todo número de Fermat composto $F_{n}=2^{2^{n}}+1\,$ pode ser decomposto em fatores primos na forma $k\ 2^{n+1}+1\,$, com $k$ inteiro positivo.
* Pode-se provar que dois números de Fermat distintos são primos entre si.
* Se $F_{n}$ é um número primo, então o polígono regular de $F_{n}$ lados pode ser construído com régua e compasso.

## Primalidade dos números de Fermat

Números de Fermat e primos de Fermat foram estudadas pela primeira vez por Pierre de Fermat, que conjecturado (mas admitiu que não poderia provar) que todos os números de Fermat são primos. De fato, os primeiros cinco números de Fermat $F_{0},\cdot \cdot \cdot ,F_{4}$ são primos. No entanto, esta conjectura foi refutada por Leonhard Euler em 1732, quando ele mostrou que
$F_{5}=2^{2^{5}}+1=2^{32}+1=4294967297=641\times 6700417.\;$
Euler provou que todo o elemento de $F_{n}$ deve ter a forma que $k2^{n+1}+1$ (depois melhorou para $k2^{n+2}+1$ por Lucas).
O fato de que 641 é um fator de $F_{5}$ pode ser facilmente deduzido a partir das igualdades $641=2^{7}*5+1$ e $641=2^{4}+5^{4}$. Segue-se a partir da primeira igualdade que $2^{7}*5\equiv -1{\pmod {641}}$ e, portanto, (elevar à quarta potência) que $2^{28}*5^{4}\equiv 1{\pmod {641}}$. Por outro lado, a segunda igualdade implica que $5^{4}\equiv -2^{4}{\pmod {641}}$. Estes congruências implica que $-2^{32}\equiv 1{\pmod {641}}$.
Acredita-se que Fermat estava ciente da forma de os fatores mais tarde comprovadas por Euler, por isso parece curioso porque ele não conseguiu acompanhar, através de cálculo simples para encontrar o fator. Uma explicação comum é que Fermat cometeu um erro computacional e estava tão convencido da justeza da sua afirmação de que ele não conseguiu verificar novamente seu trabalho.
Não existem outros números primos de Fermat conhecidos $F_{n}$ com $n>4$. No entanto, pouco se sabe sobre os números de Fermat com maiores que $n$. Na verdade, cada um dos seguintes é um problema em aberto:
* É $F_{n}$ composto para todos $n>4$ ?
* Existem infinitos números primos de Fermat ? (Eisenstein 1844)
* Existem infinitos números de Fermat compostos ?
Desde 2014 sabe-se que $F_{n}$ é composto por $5\leq n\leq 32$, embora as fatorizações completas de $F_{n}$ são conhecidas apenas para $0\leq n\leq 11$, e não há fatores conhecidos para $n=20$ e $n=24$. O maior número Fermat conhecido por ser composto é $F_{3329780}$, e suas fator primo $193*2^{3.329.782}+1$, um Megaprimo, foi descoberto pela colaboração PrimeGrid em julho de 2014.

### Argumentos heurísticos para a densidade

O seguinte argumento heurístico sugere que há apenas alguns números primos finito de Fermat: de acordo com o teorema de número primo, a "probabilidade" de que um número $n$ ser primo é, no máximo,${\frac {A}{\ln {n}}}$, em que $A$ é uma constante fixa. Portanto, o número esperado máximo de números primos Fermat é
    ${\begin{aligned}A\sum _{n=0}^{\infty }{\frac {1}{\ln F_{n}}}&={\frac {A}{\ln 2}}\sum _{n=0}^{\infty }{\frac {1}{\log _{2}(2^{2^{n}}+1)}}\\&<{\frac {A}{\ln 2}}\sum _{n=0}^{\infty }2^{-n}\\&={\frac {2A}{\ln 2}}.\end{aligned}}$
Ressalte-se que este argumento é de nenhuma maneira uma prova rigorosa. Por um lado, o argumento pressupõe que os números de Fermat se comportam "de forma aleatória", mas já vimos que os fatores de números de Fermat tem propriedades especiais.
Se (mais sofisticada) consideramos o condicional probabilidade de que $n$ é primo, uma vez que sabemos todos os seus fatores primos excedem $B$, como a mais $A{\frac {\ln {B}}{\ln {n}}}$, em seguida, usando o teorema de Euler que o fator menos nobre de $F_{n}$ excede $2^{n+1}$, encontraríamos vez
    ${\begin{aligned}A\sum _{n=0}^{\infty }{\frac {\ln 2^{n+1}}{\ln F_{n}}}&=A\sum _{n=0}^{\infty }{\frac {\log _{2}2^{n+1}}{\log _{2}(2^{2^{n}}+1)}}\\&<A\sum _{n=0}^{\infty }(n+1)2^{-n}\\&=4A.\end{aligned}}$
Embora tais argumentos geram a crença de que há apenas alguns números primos de Fermat finito, também se pode produzir argumentos para a conclusão oposta. Suponha que nós consideramos a probabilidade condicional de que $n$ seja primo, uma vez que sabemos todos os seus fatores primos são $1$ modulo $M$, como, pelo menos, ${\frac {CM}{\ln {n}}}$. Em seguida, usando o resultado de Euler que $M=2^{n+1}$ veremos que o número total esperado de números primos de Fermat seja pelo menos,
    ${\begin{aligned}C\sum _{n=0}^{\infty }{\frac {2^{n+1}}{\ln F_{n}}}&={\frac {C}{\ln 2}}\sum _{n=0}^{\infty }{\frac {2^{n+1}}{\log _{2}(2^{2^{n}}+1)}}\\&>{\frac {C}{\ln 2}}\sum _{n=0}^{\infty }1\\&=\infty ,\end{aligned}}$
e na verdade este argumento prevê que um assintoticamente fração constante dos números de Fermat são primos.

### Condições equivalentes de primalidade

Há uma série de condições que são equivalentes para a primalidade de $F_{n}$.
* Teorema de Proth (1878)—Permite que $N=k2^{m}+1$ com o antigo $k<2^{m}$. Se houver um número inteiro $a$ tal que
       $a^{\frac {N-1}{2}}\equiv -1{\pmod {N}}\!$
    Tal que $N$ seja primo. Por outro lado, se a congruência acima não ter, e além
       $\left({\frac {a}{N}}\right)=-1\!$ (Veja Símbolo de Jacobi)
    Tal que $N$ seja composto. Se $N=F_{n}>3$,
em seguida, o símbolo de Jacobi acima é sempre igual a $-1$ para $a=3$, e neste caso especial do teorema de Proth é conhecido como teste de Pépin. Embora o teste de Pépin e teorema de Proth foram implementados em computadores para provar o grau de composição de alguns números de Fermat, nem o teste dá um fator não trivial específico. Na verdade, não existe fatores primos específicos conhecidos por $n=20$ e $24$.
* Permite que $n\geq 3$ seja um inteiro positivo anterior. Tal que $n$ seja um número primo de Fermat se e apenas se a cada $a$ co-primo $n,~a$ seja um módulo de raiz primitiva $n$ se e somente se $a$ for um módulo resíduo não quadrático de $n$.
* O número de Fermat $F_{n}>3$ é primo se e apenas se puder ser escrito unicamente como uma soma de dois quadrado diferentes de zero, mais conhecido
       $F_{n}=\left(2^{2^{n-1}}\right)^{2}+1^{2}.\!$
    Quando $F_{n}=x^{2}+y^{2}$ não é da forma acima indicada, um factor adequado é:
       ${MDC}(x+2^{2^{n-1}}y,F_{n}).\!$ (Veja Máximo divisor comum)
    $Exemplo1:F_{5}=62264^{2}+20449^{2}$, assim um factor adequado é
       ${MDC}(62264\,+\,2^{2^{4}}\times 20449,\,F_{5})=641.\!$
    $Exemplo2:F_{6}=4046803256^{2}+1438793759^{2}$, assim um factor adequado é
       ${MDC}(4046803256\,+\,2^{2^{5}}\times 1438793759,\,F_{6})=274177.\!$

## Problemas em aberto

Eis algumas questões em aberto a respeito dos números de Fermat:
* Serão finitos os números primos de Fermat?
* Se são finitos, quantos são?
* Se são infinitos, serão os números compostos de Fermat finitos?
* Serão todos os números de Fermat inteiros sem fator quadrático?