Fermat Numbers: Prime Generators That Fooled a Genius

The Queen of Mathematics

Number theory is the study of the integers and the relationships between them. Despite dealing with the simplest mathematical objects, the counting numbers $ 1, 2, 3, \ldots $, it gives rise to questions of extraordinary depth and difficulty. Many problems in number theory are easy to state but have resisted the efforts of the world’s best mathematicians for centuries.

Definition (Prime Number). A prime number is an integer $ p > 1 $ whose only positive divisors are $ 1 $ and $ p $ itself. An integer $ n > 1 $ that is not prime is called composite.

The prime numbers are the fundamental building blocks of arithmetic, as expressed by the most important theorem in number theory:

Important: Fundamental Theorem of Arithmetic.
Every integer $ n > 1 $ can be written uniquely (up to order) as a product of prime numbers:
$$ n = p_1^{a_1} \, p_2^{a_2} \cdots p_k^{a_k} $$
where $ p_1 < p_2 < \cdots < p_k $ are primes and each $ a_i \geq 1 $.

Theorem (Euclid, c. 300 BCE). There are infinitely many prime numbers.

Proof. Suppose, for contradiction, that there are only finitely many primes $ p_1, p_2, \ldots, p_n $. Consider the number

$$ N = p_1 \, p_2 \cdots p_n + 1. $$

Then $ N > 1 $, so by the Fundamental Theorem of Arithmetic, $ N $ has a prime factor $ p $. But $ N $ leaves remainder 1 when divided by any $ p_i $, so $ p \neq p_i $ for all $ i $. This contradicts our assumption that $ p_1, \ldots, p_n $ is the complete list of primes.

Three themes pervade number theory and connect the topics explored in this course:

The distribution of primes. How are prime numbers scattered among the integers? Are there patterns we can exploit?
Simple rules, complex behavior. Even the most elementary operations can produce bewilderingly complex dynamics.
The gap between empirical evidence and proof. Fermat checked five cases and declared a universal truth. The Collatz conjecture has been verified for all numbers up to $ 2^{68} $. Yet in mathematics, no amount of examples constitutes a proof.

Fermat numbers and their factorizations

Definition and First Examples

Pierre de Fermat was convinced he had discovered an infinite source of prime numbers. He was wrong, and the story of how his conjecture collapsed is one of the most instructive episodes in the history of mathematics.

Definition (Fermat Number). A Fermat number is an integer of the form

$$ F_n = 2^{2^n} + 1, \qquad n \geq 0. $$

The exponent $ 2^n $ is itself a power of 2, giving Fermat numbers their double-exponential growth. This means Fermat numbers become enormous very quickly.

[Image: Table of the first several Fermat numbers showing their double-exponential growth]

The first six Fermat numbers are:

$ n $: 0 | $ 2^n $: 1 | $ F_n = 2^{2^n}+1 $: $ 2^1 + 1 = 3 $ | Prime?: Yes
$ n $: 1 | $ 2^n $: 2 | $ F_n = 2^{2^n}+1 $: $ 2^2 + 1 = 5 $ | Prime?: Yes
$ n $: 2 | $ 2^n $: 4 | $ F_n = 2^{2^n}+1 $: $ 2^4 + 1 = 17 $ | Prime?: Yes
$ n $: 3 | $ 2^n $: 8 | $ F_n = 2^{2^n}+1 $: $ 2^8 + 1 = 257 $ | Prime?: Yes
$ n $: 4 | $ 2^n $: 16 | $ F_n = 2^{2^n}+1 $: $ 2^{16} + 1 = 65{,}537 $ | Prime?: Yes
$ n $: 5 | $ 2^n $: 32 | $ F_n = 2^{2^n}+1 $: $ 2^{32} + 1 = 4{,}294{,}967{,}297 $ | Prime?: No
Why the Exponent Must Be a Power of 2

One might ask: why not study $ 2^m + 1 $ for arbitrary $ m $?

Lemma. If $ 2^m + 1 $ is prime and $ m > 0 $, then $ m $ must be a power of 2.

Proof. Suppose $ m $ has an odd factor, say $ m = ab $ with $ a > 1 $ odd. Then using the algebraic identity

$$ x^a + 1 = (x+1)(x^{a-1} – x^{a-2} + x^{a-3} – \cdots + 1) $$

with $ x = 2^b $, we get that $ (2^b + 1) \mid (2^{ab} + 1) = 2^m + 1 $. Since $ 1 < 2^b + 1 < 2^m + 1 $, the number $ 2^m + 1 $ is composite. Therefore, if $ 2^m + 1 $ is prime, $ m $ can have no odd factor greater than 1, meaning $ m = 2^n $ for some $ n \geq 0 $.

Fermat’s Conjecture and Euler’s Refutation

Fermat examined $ F_0 $ through $ F_4 $, found them all prime, and wrote to Marin Mersenne:

“I have found that numbers of the form $ 2^{2^n} + 1 $ are always prime numbers and have long since signified to analysts the truth of this theorem.”

Fermat admitted he could not prove this. He had checked five cases and assumed the pattern would continue. It did not.

In 1732, nearly a century after Fermat’s death, Leonhard Euler showed that $ F_5 $ is composite:

Important: Euler’s Discovery (1732).
$$ F_5 = 2^{32} + 1 = 4{,}294{,}967{,}297 = 641 \times 6{,}700{,}417. $$

The lesson is profound: in mathematics, five examples are not a proof. Even a million examples are not a proof.

Bennett’s Elegant Proof That 641 Divides F_5

The following elementary proof, due to G. Bennett, requires no computer, only clever algebraic manipulation.

Theorem. $ 641 $ divides $ F_5 = 2^{32} + 1 $.

Proof. Let $ a = 5 $ and $ b = 2^7 = 128 $. Observe that:

$ ab + 1 = 5 \times 128 + 1 = 641 $
$ a^4 = 5^4 = 625 $

From these, $ 2^4 = 16 = 641 – 625 = (ab + 1) – a^4 $, so

$$ 2^4 = 1 + ab – a^4. $$

Now rewrite $ F_5 $:

$$ F_5 = 2^{32} + 1 = (2^4) \cdot (2^7)^4 + 1 = 2^4 \cdot b^4 + 1. $$

We proceed using modular arithmetic. From $ 641 = 5^4 + 2^4 $, we get $ 5^4 \equiv -2^4 \pmod{641} $, hence

$$ 5^4 \cdot 2^{28} \equiv -2^{32} \pmod{641}. $$

Also $ 641 = 5 \cdot 2^7 + 1 $ gives $ 5 \cdot 2^7 \equiv -1 \pmod{641} $, so

$$ 5^4 \cdot 2^{28} \equiv (-1)^4 = 1 \pmod{641}. $$

Combining: $ -2^{32} \equiv 1 \pmod{641} $, which means $ 2^{32} + 1 \equiv 0 \pmod{641} $.

Therefore $ 641 \mid F_5 $.

The other factor is $ 6{,}700{,}417 $. Both $ 641 $ and $ 6{,}700{,}417 $ are prime, so $ F_5 = 641 \times 6{,}700{,}417 $ is the complete prime factorization.

Key Properties of Fermat Numbers

Mutual Coprimality

Theorem (Goldbach, 1730). For any two distinct Fermat numbers $ F_m $ and $ F_n $ with $ m \neq n $:

$$ \gcd(F_m, F_n) = 1. $$

This property has a beautiful consequence:

Corollary (Infinitude of Primes via Fermat Numbers). There are infinitely many prime numbers.

Proof. Each Fermat number $ F_n \geq 3 $ has at least one prime factor. Since no two Fermat numbers share a prime factor, and there are infinitely many Fermat numbers, there must be infinitely many primes.

To prove the coprimality theorem, we first need a recursive relationship.

Lemma (Recursive Formula). For all $ n \geq 1 $:

$$ F_n = F_0 \cdot F_1 \cdot F_2 \cdots F_{n-1} + 2. $$

Proof. We prove this by induction on $ n $.

Base case: $ n = 1 $. We have $ F_0 + 2 = 3 + 2 = 5 = F_1 $.

Inductive step: Assume $ F_n = F_0 F_1 \cdots F_{n-1} + 2 $. We need to show $ F_{n+1} = F_0 F_1 \cdots F_n + 2 $. Note that

$$ F_{n+1} = 2^{2^{n+1}} + 1 = \bigl(2^{2^n}\bigr)^2 + 1 = (F_n – 1)^2 + 1 = F_n^2 – 2F_n + 2. $$

By the inductive hypothesis, $ F_0 F_1 \cdots F_{n-1} = F_n – 2 $, so:

$$ \begin{aligned} F_0 F_1 \cdots F_n + 2 &= (F_n – 2) \cdot F_n + 2 \\ &= F_n^2 – 2F_n + 2 \\ &= F_{n+1}. \end{aligned} $$

Proof of the Coprimality Theorem. Without loss of generality, assume $ m > n \geq 0 $. Let $ d = \gcd(F_m, F_n) $. By the recursive formula:

$$ F_m = F_0 F_1 \cdots F_{m-1} + 2. $$

Since $ n < m $, $ F_n $ appears among $ F_0, \ldots, F_{m-1} $, so $ F_n \mid (F_m – 2) $. Hence $ d \mid F_m $ and $ d \mid F_n \mid (F_m – 2) $, which gives $ d \mid (F_m – (F_m – 2)) = 2 $.

So $ d \in \{1, 2\} $. But every Fermat number is odd (since $ 2^{2^n} $ is even, $ 2^{2^n}+1 $ is odd), so $ d $ must be odd. Therefore $ d = 1 $.

The Euler-Lucas Factoring Theorem

Theorem (Euler-Lucas). Any prime factor $ p $ of $ F_n $ (where $ n \geq 2 $) has the form

$$ p = k \cdot 2^{n+2} + 1 $$

for some positive integer $ k $.

This theorem dramatically narrows the search for factors of Fermat numbers. For $ F_5 $, it tells us to check primes of the form $ 128k + 1 $. Indeed, $ 641 = 5 \times 128 + 1 $ fits this pattern with $ k = 5 $.

Applying the Euler-Lucas theorem to $ F_5 $: any prime factor must have the form $ 2^7 \cdot k + 1 = 128k + 1 $. The first few candidates are:

$$ 129 = 3 \times 43, \quad 257 = F_3, \quad 385 = 5 \times 77, \quad 513 = 3^3 \times 19, \quad 641 = \text{prime!} $$

Testing $ 641 $: we find $ 641 \mid F_5 $, confirming the factorization.

Connection to Constructible Polygons

One of the most beautiful connections in mathematics links Fermat primes to classical geometry.

Important: Gauss-Wantzel Theorem.
A regular $ n $-gon is constructible with compass and straightedge if and only if
$$ n = 2^a \cdot p_1 \cdot p_2 \cdots p_k $$
where $ a \geq 0 $ and $ p_1, p_2, \ldots, p_k $ are distinct Fermat primes.

Since only five Fermat primes are known ($ 3, 5, 17, 257, 65537 $), the number of constructible regular $ n $-gons with $ n $ odd is severely limited. For example, the regular 17-gon is constructible (Gauss famously proved this in 1796, which solidified his decision to pursue mathematics), but the regular 7-gon is not.

Pepin’s Primality Test

Theorem (Pepin, 1877). For $ n \geq 1 $, the Fermat number $ F_n $ is prime if and only if

$$ 3^{(F_n – 1)/2} \equiv -1 \pmod{F_n}. $$

Pepin’s test is a complete characterization: it is both necessary and sufficient for primality. The base 3 can be replaced by any quadratic non-residue modulo $ F_n $. This test can prove a Fermat number is composite even when we cannot find its prime factors, we simply compute the modular exponentiation.

Current State of Knowledge

As of 2026, the status of Fermat numbers is as follows:

Status: Confirmed prime | Values of $ n $: 0, 1, 2, 3, 4
Status: Completely factored | Values of $ n $: 5, 6, 7, 8, 9, 10, 11
Status: Known composite, partial factorization | Values of $ n $: 12, 13, 14, …
Conjecture. There are only five Fermat primes: $ F_0 = 3 $, $ F_1 = 5 $, $ F_2 = 17 $, $ F_3 = 257 $, and $ F_4 = 65{,}537 $. No further Fermat number is prime.

Most number theorists believe this conjecture is true, but it remains unproven.

Fermat Number Factoring Data

$ n $: 0 | $ F_n $: 3 | Status: Prime | Smallest prime factor: —
$ n $: 1 | $ F_n $: 5 | Status: Prime | Smallest prime factor: —
$ n $: 2 | $ F_n $: 17 | Status: Prime | Smallest prime factor: —
$ n $: 3 | $ F_n $: 257 | Status: Prime | Smallest prime factor: —
$ n $: 4 | $ F_n $: 65,537 | Status: Prime | Smallest prime factor: —
$ n $: 5 | $ F_n $: 4,294,967,297 | Status: Composite | Smallest prime factor: 641
$ n $: 6 | $ F_n $: ~1.84 x 10^19 | Status: Composite | Smallest prime factor: 274,177
$ n $: 7 | $ F_n $: ~3.40 x 10^38 | Status: Composite | Smallest prime factor: 59,649,589,127,497,217
$ n $: 8 | $ F_n $: ~1.16 x 10^77 | Status: Composite | Smallest prime factor: 1,238,926,361,552,897

Exercises:

Verify that $ F_0, F_1, F_2, F_3 $ are prime by checking for divisors up to their square roots.

Use the Euler-Lucas theorem to determine what form the prime factors of $ F_6 $ must have. Then verify that $ 274{,}177 $ fits this form.

Prove that $ F_n \equiv 2 \pmod{3} $ for all $ n \geq 1 $, and explain why 3 can never divide a Fermat number other than $ F_0 $.

Using the recursive formula $ F_n = F_0 F_1 \cdots F_{n-1} + 2 $, compute $ F_4 $ step by step from the product of $ F_0, F_1, F_2, F_3 $.

The Gauss-Wantzel theorem states that a regular $ n $-gon is constructible if and only if $ n = 2^a p_1 p_2 \cdots p_k $ where the $ p_i $ are distinct Fermat primes. List all constructible regular $ n $-gons for odd $ n \leq 300 $.

Apply Pepin’s test conceptually: if $ 3^{(F_2 – 1)/2} = 3^8 = 6561 $, compute $ 6561 \bmod 17 $ and verify the test predicts $ F_2 = 17 $ is prime.