Fermat Number - Primality of Fermat Numbers

Primality of Fermat Numbers

Fermat numbers and Fermat primes were first studied by Pierre de Fermat, who conjectured (but admitted he could not prove) that all Fermat numbers are prime. Indeed, the first five Fermat numbers F₀,...,F₄ are easily shown to be prime. However, this conjecture was refuted by Leonhard Euler in 1732 when he showed that

Euler proved that every factor of F_n must have the form k2n+1 + 1 (later improved to k2n+2 + 1 by Lucas).

The fact that 641 is a factor of F₅ can be easily deduced from the equalities 641 = 27×5+1 and 641 = 24 + 54. It follows from the first equality that 27×5 ≡ −1 (mod 641) and therefore (raising to the fourth power) that 228×54 ≡ 1 (mod 641). On the other hand, the second equality implies that 54 ≡ −24 (mod 641). These congruences imply that −232 ≡ 1 (mod 641).

It is widely believed that Fermat was aware of the form of the factors later proved by Euler, so it seems curious why he failed to follow through on the straightforward calculation to find the factor. One common explanation is that Fermat made a computational mistake and was so convinced of the correctness of his claim that he failed to double-check his work.

There are no other known Fermat primes F_n with n > 4. However, little is known about Fermat numbers with large n. In fact, each of the following is an open problem:

• Is F_n composite for all n > 4?
• Are there infinitely many Fermat primes? (Eisenstein 1844)
• Are there infinitely many composite Fermat numbers?

As of 2010 it is known that F_n is composite for 5 ≤ n ≤ 32, although complete factorizations of F_n are known only for 0 ≤ n ≤ 11, and there are no known factors for n in {20, 24}. The largest Fermat number known to be composite is F_2543548, and its prime factor 9×22543551 + 1 was discovered by Scott Brown in PrimeGrid's Proth Prime Search on June 22, 2011.