Aiichi Yamasaki's Homepage

a3f

Fermat numbers

A Fermat number is an integer of the form $F_n=2^{2^n}+1$. A Fermat prime is a Fermat number that is prime. $F_0=3,$ $F_1=5,$ $F_2=17,$ $F_3=257,$ $F_4=65537$ are all Fermat primes. Fermat conjectured in 1640 that all the Fermat numbers are prime. However Euler calculated in 1732 that \[F_5=641\times6700417.\] (All the other propositions Fermat claimed are proved to be correct).

Fermat's little theorem shows that all the prime factor of $F_n$ must be of the form $k \cdot 2^{n+1}+1$. Euler tried to divide $F_5$ by the numbers 193, 257, 449, 577, 641 to find the factor 641. In 1877, Lucas used this fact to show that \[F_6=274177\times67280421310721.\]

Pépin found in 1877 an efficient method for testing the primality of $F_n$.
$F_n$ is prime if and only if $3^{(F_n-1)/2} \equiv -1 \pmod{F_n}$.
The compositeness of $F_7$ was proved in 1905 using Pépin's test.

As of 2017, $F_n$ is known to be composite for $5 \leq n \leq 32$. $F_{20}$ and $F_{24}$ are composite, but no prime factors are known. As for $F_{14}$ and $F_{22}$, prime factors were not known for a long time, but the prime factor of each of them were found in 2010). The compositeness of $F_{24}$ was proved in 1999 using Pépin's test. It took about half year at that time. The primality status of $F_{33}$ is unknown. It takes too much time to perform Pépin's test on $F_{33}$ even with a supercomputer.

In 1970, Morrison and Brillhart used continued fractions factoring method to show that \[F_7= 59649589127497217 \times 5704689200685129054721.\] In 1980, Brent and Pollard used ρ-method to show that \[F_8= 1238926361552897 \times p_{62},\] where $p_n$ is a $n$-digit prime number.

In 1988, Brent used ECM (elliptic curve method) to show that \[F_{11}= 319489 \times 974849 \times 167988556341760475137 \times\] \[3560841906445833920513 \times p_{564}.\]

In 1989, Lenstra and Manasse used NFS (number field sieve) to show that \[\begin{eqnarray*} F_9 &=& 2424833 \times p_{49} \times p_{99}, \\ p_{49} &=& \small{7455602825647884208337395736200454918783366342657}. \end{eqnarray*}\]

ECM and NFS are both fast algorithms for integer factorization. Expected running time of ECM depends on the size of prime factors, whereas expected running time of NFS depends on the size of composite numbers to factor.

In 1995, Brent used ECM to show that \[\begin{eqnarray*} F_{10} &=& 45592577 \times 6487031809 \times p_{40} \times p_{252}, \\ p_{40} &=& 4659775785220018543264560743076778192897. \end{eqnarray*}\]