1.1 A Prime Factory — Beyond STEP

The question

The $n$th Fermat number, $F_n$, is defined by \[F_n = 2^{2^n} + 1, \qquad n = 0, 1, 2, \ldots,\] where $2^{2^n}$ means $2$ raised to the power $2^n$.

Calculate $F_0$, $F_1$, $F_2$ and $F_3$. Show that, for $k = 1$, $k = 2$ and $k = 3$, \[F_0 F_1 \cdots F_{k-1} = F_k - 2. \tag{$*$}\] Prove, by induction or otherwise, that $(*)$ holds for all $k \geq 1$. Deduce that no two Fermat numbers have a common factor greater than $1$.

Hence show that there are infinitely many prime numbers.

The hook

You almost certainly already know that there are infinitely many primes. Euclid proved it around 300 BC, and it is one of the first proofs anyone meets. So why would a STEP question ask you to prove it again?

Because this proof works in a completely different way. Euclid’s argument says: give me any finite list of primes and I will show you it is incomplete. This one says: here is a single, explicit sequence of numbers, written down in advance, and every one of them contains a prime that none of the others contain. It is a machine for manufacturing new primes, and the reason it works is a beautifully simple identity that the question walks you towards.

Along the way you will meet numbers that fooled Fermat himself.

Before you start

Read the question through once and notice its shape. It has four stages:

compute some examples;
spot (well, be told) a pattern, and check it on those examples;
prove the pattern in general;
use the pattern twice: first to deduce something about common factors, then something about primes.

This “examples $\to$ conjecture $\to$ proof $\to$ consequences” structure is how a great deal of mathematics is actually done, and STEP questions often follow it. When you see it, the early parts are usually not just warm-up: they are where you build the intuition you will need later.

The last line asks about infinitely many primes. The middle asks about common factors. What could possibly connect “no two Fermat numbers share a factor” with “there are infinitely many primes”?

Hold on to that question. We will come back to it.

Working it through

Stage 1 Getting a feel for the numbers

Be careful with the notation: $2^{2^n}$ means $2^{(2^n)}$, not $(2^2)^n$. The exponent is itself a power of 2, so these numbers grow very fast. \[\begin{aligned} F_0 &= 2^{1} + 1 = 3, &\qquad F_2 &= 2^{4} + 1 = 17,\\ F_1 &= 2^{2} + 1 = 5, &\qquad F_3 &= 2^{8} + 1 = 257. \end{aligned}\]

What do you notice about these four numbers?

They are all prime. (Check $257$: it is not divisible by $2, 3, 5, 7, 11$ or $13$, and $17^2 = 289 > 257$, so we can stop.) The next one, $F_4 = 2^{16} + 1 = 65537$, is also prime. Pierre de Fermat noticed exactly this in 1640 and conjectured that every number of this form is prime. Keep that in mind; we will see later whether he was right.

Stage 2 Checking the identity

Now check $(*)$ for small $k$:

$k = 1$: the left-hand side is just $F_0 = 3$, and $F_1 - 2 = 3$.
$k = 2$: $F_0 F_1 = 3 \times 5 = 15$, and $F_2 - 2 = 15$.
$k = 3$: $F_0 F_1 F_2 = 15 \times 17 = 255$, and $F_3 - 2 = 255$.

Look at the step from $k = 2$ to $k = 3$. We took $15$, multiplied by $17$, and got $255$. In terms of Fermat numbers, we computed $(F_2 - 2) \times F_2$ and got $F_3 - 2$. Is that a coincidence?

That observation is the whole proof in miniature. Let’s see why it should be true.

Stage 3 Proving the identity

Before reading on, try to show directly that \[(F_k - 2)\, F_k = F_{k+1} - 2.\] Hint: write everything in terms of powers of 2. What does $F_k - 2$ look like?

We have $F_k - 2 = 2^{2^k} - 1$ and $F_k = 2^{2^k} + 1$, so \[(F_k - 2)\, F_k = \bigl(2^{2^k} - 1\bigr)\bigl(2^{2^k} + 1\bigr).\]

This is a product of the form $(a - 1)(a + 1)$. What is that?

It is a difference of two squares, $a^2 - 1$. With $a = 2^{2^k}$, \[a^2 = \bigl(2^{2^k}\bigr)^2 = 2^{2 \cdot 2^k} = 2^{2^{k+1}},\] so \[(F_k - 2)\, F_k = 2^{2^{k+1}} - 1 = F_{k+1} - 2. \tag{$\dagger$}\] That is the engine. Notice what squaring does: it doubles the exponent, and doubling $2^k$ gives $2^{k+1}$. The definition of the Fermat numbers is perfectly tuned to the difference-of-squares factorisation.

Now the induction is almost automatic.

What exactly do we need to show in the inductive step?

We assume $(*)$ holds for some $k \geq 1$, \[F_0 F_1 \cdots F_{k-1} = F_k - 2,\] and we want to show it holds for $k + 1$: \[F_0 F_1 \cdots F_{k-1} F_k = F_{k+1} - 2.\] Multiply both sides of the assumption by $F_k$ and use $(\dagger)$: \[F_0 F_1 \cdots F_{k-1} F_k = (F_k - 2)\, F_k = F_{k+1} - 2.\] We have already checked $k = 1$, so by induction $(*)$ holds for every $k \geq 1$.■

Could we have avoided induction altogether?

Yes, and it is worth seeing how. Apply $(\dagger)$ repeatedly, starting from $F_0 - 2 = 1$: \[F_k - 2 = (F_{k-1} - 2) F_{k-1} = (F_{k-2} - 2) F_{k-2} F_{k-1} = \cdots = (F_0 - 2)\, F_0 F_1 \cdots F_{k-1}.\] Since $F_0 - 2 = 1$, we are done. This “unrolling” is really the same induction written out in full, but some people find it easier to see.

Stage 4 No common factors

We want to show that if $m \neq n$ then $F_m$ and $F_n$ have no common factor greater than $1$.

Suppose some number $d$ divides both $F_m$ and $F_n$, with $m < n$. Where does $F_m$ appear in $(*)$?

Take $k = n$ in $(*)$: \[F_0 F_1 \cdots F_m \cdots F_{n-1} = F_n - 2.\] Since $m < n$, the number $F_m$ is one of the factors on the left. So if $d$ divides $F_m$, then $d$ divides the whole left-hand side; that is, $d$ divides $F_n - 2$.

Now $d$ divides $F_n$ and $F_n - 2$. What else must it divide?

Their difference: $d$ divides $F_n - (F_n - 2) = 2$. So $d = 1$ or $d = 2$.

Can $d$ be $2$?

No: every Fermat number is a power of 2 plus 1, so it is odd. Hence $d = 1$, and no two distinct Fermat numbers share a factor greater than $1$.■

Mathematicians say the Fermat numbers are pairwise coprime.

Stage 5 Infinitely many primes

Now we return to the question we asked at the start.

Every whole number greater than $1$ has at least one prime factor. Pick one prime factor of each Fermat number. What can you say about the primes you have picked?

Let $p_n$ be any prime that divides $F_n$. If two of these were equal, say $p_m = p_n$ with $m \neq n$, then that prime would be a common factor of $F_m$ and $F_n$ greater than $1$, which we have just shown is impossible. So the primes \[p_0,\; p_1,\; p_2,\; p_3,\; \ldots\] are all different. There are infinitely many Fermat numbers, so there are infinitely many different primes.■

Notice that we never needed to know which prime divides each Fermat number, or even whether the Fermat numbers are themselves prime. All we needed was that they never share a factor. Each one is forced to “use up” at least one prime that no other can use.

Looking back

It is worth pausing to see what made this work, because the same ideas will come back many times in this book.

The examples weren’t decoration. Spotting that $15 \times 17 = 255$ was “$(F_2 - 2) \times F_2 = F_3 - 2$” was the key idea. When a question gives you small cases, ask what each step is doing, not just whether the numbers match.
A single identity did all the work. Everything flowed from $(a-1)(a+1) = a^2 - 1$. Hard-looking STEP questions are often driven by one simple piece of algebra.
The final argument is about structure, not size. We proved there are infinitely many primes without finding a single new one. Instead we showed that an infinite family of numbers needs infinitely many primes to build them.

What’s really going on

Was Fermat right?

No. In 1732 Leonhard Euler showed that \[F_5 = 2^{32} + 1 = 4\,294\,967\,297 = 641 \times 6\,700\,417.\] Euler didn’t find $641$ by luck. He proved that any prime factor of $F_n$ must have a very special form (for $n = 5$, it must be one more than a multiple of $64$), which drastically cut down the candidates. You can prove this yourself in Exercise 4.

Since then, every Fermat number anyone has managed to test, from $F_5$ up to $F_{32}$, has turned out to be composite. As far as anyone knows, $F_0$ to $F_4$ may be the only Fermat primes, but nobody has been able to prove it. It is a genuinely open problem.

The delightful twist is that our proof doesn’t care. Prime or composite, the Fermat numbers still produce infinitely many primes.

Fermat primes and constructing polygons

Fermat primes turn up somewhere quite unexpected. The ancient Greeks knew how to construct an equilateral triangle and a regular pentagon with ruler and compass, and notice that $3 = F_0$ and $5 = F_1$. For two thousand years nobody could construct any other regular polygon with a prime number of sides. Then in 1796, aged 19, Carl Friedrich Gauss showed how to construct a regular 17-gon, and $17 = F_2$.

Gauss went further: a regular $N$-gon can be constructed with ruler and compass exactly when $N$ is a power of 2 multiplied by distinct Fermat primes. (Pierre Wantzel completed the proof in 1837.) So which polygons can be constructed depends on how many Fermat primes there are. You will meet the key calculation behind Gauss’s 17-gon in Section 6.2 (STEP II 1991, Question 4), and the full story belongs to Galois theory, one of the highlights of an undergraduate degree.

One theorem, many proofs

Why would mathematicians bother proving the same theorem more than once? Because different proofs reveal different things. This proof, usually credited to Christian Goldbach in a 1730 letter to Euler, shows that any infinite sequence of pairwise coprime whole numbers greater than 1 forces infinitely many primes. Fermat numbers are just one convenient example. (Exercise 3 gives another.)

It also gives more than Euclid’s proof does. The primes $p_0, p_1, \ldots, p_{n-1}$ are $n$ different primes, each at most $F_{n-1}$. So there are at least $n$ primes no bigger than $2^{2^{n-1}} + 1$. That is a quantitative statement about how the primes are spread out. It is very weak (the truth is much better), but it is a first step towards one of the great results of nineteenth-century mathematics, the Prime Number Theorem, which describes exactly how the primes thin out. Section 1.2 takes the next step.

The thinking skill

Building an argument from a structural property

To show that infinitely many objects of type A exist, find infinitely many objects of type B, each of which needs its own object of type A.

Here A = primes and B = Fermat numbers, and “needs its own” means “has a prime factor not shared with any other”. The same pattern appears in counting arguments, in linear algebra (infinitely many independent vectors force infinite dimension) and in analysis.

You also practised induction, and in particular the habit of asking “what does the step from $k$ to $k+1$ actually do?” That question is often more useful than the formal template.

Try this next

Euclid’s version. Write out Euclid’s proof that there are infinitely many primes. In what sense is it “by contradiction”, and in what sense is the Fermat-number proof “constructive”?
The last digit. Show that for $n \geq 2$ the Fermat number $F_n$ ends in the digit $7$.
Sylvester’s sequence. Define $a_1 = 2$ and $a_{n+1} = a_n^2 - a_n + 1$, so the sequence begins $2, 3, 7, 43, 1807, \ldots$
1. Show that $a_{n+1} - 1 = a_1 a_2 \cdots a_n$.
2. Deduce that the terms are pairwise coprime, and hence give another proof that there are infinitely many primes.
3. harder Show that $\dfrac{1}{a_1} + \dfrac{1}{a_2} + \cdots + \dfrac{1}{a_n} = 1 - \dfrac{1}{a_{n+1} - 1}$.
Euler’s trick. This needs Fermat’s Little Theorem: if $p$ is prime and $p \nmid a$, then $a^{p-1} \equiv 1 \pmod{p}$. Suppose a prime $p$ divides $F_n$.
1. Show that $2^{2^n} \equiv -1 \pmod p$, and hence that $2^{2^{n+1}} \equiv 1 \pmod p$.
2. Let $d$ be the smallest positive integer with $2^d \equiv 1 \pmod p$. Show that $d$ divides $2^{n+1}$ but not $2^n$, and conclude that $d = 2^{n+1}$.
3. Using Fermat’s Little Theorem, show that $d$ divides $p - 1$. Deduce that $p \equiv 1 \pmod{2^{n+1}}$.
4. For $n = 5$, this says any prime factor of $F_5$ has the form $64k + 1$. Check that $641$ does. How many primes of this form are smaller than $641$?
A bound on the primes. Use the argument in One theorem, many proofs to show that the $n$th prime is at most $2^{2^{n-1}} + 1$. How good is this bound when $n = 5$?

A Prime Factory