Número de Fermat

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em Matemática, um número de Fermat é um número inteiro positivo que assume a forma:[1]

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 esses números eram primos.[1] Mas mais tarde Leonard Euler provou que não era assim; para n = 5 obtinha-se um número composto:[1]

 F_{5} = 2^{2^5} + 1 = 2^{32} + 1 = 4294967297 = 641 \cdot 6700417 \;

Até hoje só são conhecidos cinco números primos de Fermat, e não se sabe se há mais ou não:[1]

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,[2] bem como, números enormes como F_{23288}\, e F_{23471}\, são comprovadamente compostos.

Propriedades dos números de Fermat[editar | editar código-fonte]

  • Um número de Fermat é igual ao produto de todos os anteriores mais 2.[1]

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 \,\!


Primalidade dos números de Fermat[editar | editar código-fonte]


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 facilmente demonstrado ser nobre. 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 k 2^{n + 1} + 1 (depois melhorou para k 2^{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.[3] 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.[4] Na verdade, cada um dos seguintes é um problema em aberto:

Desde de 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.[6] 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.[6] [7]


Argumentos heurísticos para a densidade[editar | editar código-fonte]

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{align}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{align}

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{align}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{align}

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{align}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{align}

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[editar | editar código-fonte]

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)
Exemplo 1 : F_5 = 62264^2 + 20449^2, assim um factor adequado é
{MDC} (62264\, +\, 2^{2^4}\times 20449,\, F_{5}) = 641.\!
Exemplo 2 : F_6 = 4046803256^2 + 1438793759^2, assim um factor adequado é
{MDC} (4046803256\, +\, 2^{2^5}\times 1438793759,\, F_{6}) = 274177.\!

Problemas em aberto[editar | editar código-fonte]

Eis algumas questões em aberto a respeito dos números de Fermat:

  • Serão finitos os números primos de Fermat?[1]
  • 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?

Ver também[editar | editar código-fonte]

Referências

  1. a b c d e f g h Chris K. Caldwell, The Prime Glossary, Fermat number[em linha] (em inglês)
  2. Prime Curios!. (em inglês)
  3. Křížek, Luca & Somer 2001, p. 38, Remark 4.15
  4. Chris Caldwell, "Prime Links++: special forms" at The Prime Pages.
  5. Ribenboim 1996, p. 88.
  6. a b Keller, Wilfrid (February 7, 2012), Prime Factors of Fermat Numbers (em inglês)
  7. PrimeGrid’s Mega Prime Search - 193*2^3329782+1 (official announcement) PrimeGrid. Visitado em 7 August 2014.

Bibliografia[editar | editar código-fonte]

  1. Michal Krizek, Florian Luca, Lawrence Somer, 17 Lectures on Fermat Numbers: From Number Theory to Geometry, Springer Science & Business Media, 2001 ISBN 0-387-95332-9 (em inglês)
  2. David Wells, Prime Numbers: The Most Mysterious Figures in Math, John Wiley & Sons, 2011 ISBN 1-118-04571-8 (em inglês)
  3. Daniel Zwillinger, CRC Standard Mathematical Tables and Formulae, 31st Edition, CRC Press, 2002. ISBN 1-420-03534-7. (em inglês)
  4. James K. Strayer, Elementary Number Theory, Waveland Press, 2001 ISBN 1-478-61040-9 (em inglês)
  5. Ribenboim, Paulo (1996), The New Book of Prime Number Records (3rd ed.), New York: Springer, ISBN 0-387-94457-5 (em inglês)

Ligações externas[editar | editar código-fonte]

Portal A Wikipédia possui o
Portal da Matemática.
Ícone de esboço Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.