Mathematicians have always dreamed of a formula that produces only prime numbers. In 1640 Fermat thought he had found one.

Five primes in a row

Fermat studied numbers of the form

$$F_n=2^{2^n}+1.$$

The exponent is a power of 2: $1,2,4,8,16,\ldots$ Computing the first few:

$$F_0=3,\quad F_1=5,\quad F_2=17,\quad F_3=257,\quad F_4=65{,}537.$$

All five are prime. Checking $65{,}537$ by hand, trying divisors up to its square root, was already hard work. Fermat wrote to Frénicle de Bessy that he was convinced all numbers of this form were prime, although he admitted he had no proof.

A number too large

The next on the list is

$$F_5=2^{32}+1=4{,}294{,}967{,}297.$$

A ten-digit number. To test whether it is prime, you would need to try divisors up to about 65,000, by hand, in the 17th century. Fermat did not do the calculation.

Almost a hundred years later, in 1732, the young Leonhard Euler did. And he found:

$$4{,}294{,}967{,}297=641\times6{,}700{,}417.$$

Fermat’s conjecture was wrong. A single counterexample is enough to bring down a statement about all numbers.

Why 641?

Euler did not try divisors at random. He knew that the divisors of $F_5$ had to have a special form, $64k+1$, which greatly reduced the search. The fifth prime candidate of that form is 641.

There is also an elegant way to verify the divisibility without doing the division. Notice that 641 can be written in two ways:

$$641=5\cdot2^7+1=5^4+2^4.$$

Modulo 641, the first form says that $5\cdot2^7$ leaves remainder $-1$. Raising to the fourth power, $5^4\cdot2^{28}$ leaves remainder $1$. The second form says that $5^4$ leaves the same remainder as $-2^4$. Swapping one for the other:

$$-2^4\cdot2^{28}=-2^{32}\equiv1\pmod{641}.$$

So $2^{32}+1$ leaves remainder 0: it is a multiple of 641. The full calculation is in the Euler trail.

An unexpected use: the 17-sided polygon

Since the Greeks, people knew how to construct the regular triangle and pentagon with ruler and compass. For two thousand years nobody managed to construct another regular polygon with a prime number of sides.

In 1796, at 18, Carl Friedrich Gauss showed that the heptadecagon, the regular 17-sided polygon, can be constructed. And he went further: a polygon with a prime number of sides can be constructed with ruler and compass only if that prime is a Fermat prime. Notice: $3=F_0$, $5=F_1$, $17=F_2$. The next would be $257$ and $65{,}537$. See the construction in the Gauss trail.

Fermat’s conjecture was wrong, but the numbers it studied were exactly the right ones for another question.

Exercise: F₁ = 5 and F₂ = 17 are prime. Is that enough to prove all Fₙ are prime?

No. They are particular cases. A statement about every index needs a general proof, and $F_5$ shows it is false.

Exercise: show that Fₙ − 2 = F₀ · F₁ ⋯ Fₙ₋₁ for n = 3

$F_0F_1F_2=3\cdot5\cdot17=255$ and $F_3-2=257-2=255$. The identity holds for every $n$ and shows that two different Fermat numbers never share a factor. From this comes a new proof that there are infinitely many primes.

Sources: Fermat biography, MacTutor.

All Fermat topics · ← Fermat’s little theorem: powers and remainders · Fermat and Pascal: fairly dividing an interrupted game →

Image credits.