Pierre de Fermat believed that all numbers of the form $2^{2^n} + 1$ were prime. For $n = 0, 1, 2, 3, 4$ works: 3, 5, 17, 257 and 65 537 are primes. The next one is

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

Testing all dividers by hand is impractical. In 1732, Euler showed that this number is divisible by 641. An elegant way to look at this uses two ways of writing 641:

$$641 = 5 \cdot 2^7 + 1 \qquad\text{e}\qquad 641 = 5^4 + 2^4.$$

Working with remainders from division by 641 (the symbol $\equiv$ means “leave the same remainder”):

Deduction in four steps (click to advance)

  1. In the first way, $5 \cdot 2^7 \equiv -1$. Raising to the fourth power: $5^4 \cdot 2^{28} \equiv 1$.
  2. In the second way, $5^4 \equiv -2^4$.
  3. Replacing step 2 with step 1: $-2^4 \cdot 2^{28} \equiv 1$, that is, $-2^{32} \equiv 1$.
  4. Therefore $2^{32} + 1 \equiv 0$: the number is a multiple of 641.

In fact, 4 294 967 297 = 641 × 6 700 417. To this day, no other number is known of Fermat prime beyond the top five.

All topics by Leonhard Euler · ← Infinite prime numbers from a sum · Euler’s theorem and cryptography →

Credits and sources of images.