Solution to problem 28

To begin with, we have by direct calculation that ${F}_{0}=3\phantom{\rule{0.3em}{0ex}}$, ${F}_{1}=5\phantom{\rule{0.3em}{0ex}}$, ${F}_{2}=17\phantom{\rule{0.3em}{0ex}}$ and ${F}_{3}=257$, so it is easy to verify ($\ast$) for $k=1,2$ and $3$.

For the induction, we start by assuming that the result holds for $k=m\phantom{\rule{0.3em}{0ex}}$ so that

${F}_{0}{F}_{1}\dots {F}_{m-1}={F}_{m}-2\phantom{\rule{2.77695pt}{0ex}}.$

We need to show that this implies that the result holds for $k=m+1$, i.e. that

${F}_{0}{F}_{1}\dots {F}_{m}={F}_{m+1}-2\phantom{\rule{2.77695pt}{0ex}}.$

Starting with the left hand side of this equation, we have

${F}_{0}{F}_{1}\dots {F}_{m-1}{F}_{m}=\left({F}_{m}-2\right){F}_{m}=\left({2}^{{2}^{m}}-1\right)\left({2}^{{2}^{m}}+1\right)={\left({2}^{{2}^{m}}\right)}^{2}-1={2}^{{2}^{m+1}}-1={F}_{m+1}-2,$

as required. Since we know that the result holds for $k=1$, the induction is complete.

To show that no two Fermat number have a common factor (other than 1), we proceed by contradiction. Suppose $p$ divides ${F}_{l}$ and ${F}_{m}$, where $l. Then $p$ divides ${F}_{0}{F}_{1}\dots {F}_{l}\dots {F}_{m-1}$ and therefore $p$ divides ${F}_{m}-2$, by $\left(\ast \right)$, as well as ${F}_{m}$. But this is impossible: all Fermat numbers are odd so no number other than 1 divides both ${F}_{m}-2$ and ${F}_{m}$. Hence no two Fermat numbers have a common factor greater than 1.

For the last part, note that every number can be written uniquely as a product of prime factors and that because the Fermat numbers are co-prime, each prime can appear in at most one Fermat number. Thus, since there are inﬁnitely many Fermat numbers, there must be inﬁnitely many primes.

Post-mortem

This question is largely about proof. The above solution has a proof by induction and a proof by contradiction. The last part could have been written as a proof by contradiction too.

The difficulty is in presenting the proof. It is not enough to understand your own proof: you have to be able to set it out so that it is clear to the reader. This is a vital part of mathematics and its most useful transferable skill.

At the meeting in which this question was ﬁrst considered, one of the examiners said that he didn’t see the point of the question, since there is already a well-known proof (due to Euclid, possibly) that there are inﬁnitely many primes. As mentioned overleaf, this proof is due to Goldbach, and I could only respond that if Goldbach thought it worthwhile, that was good enough for me.

21 M. Aigler and G.M. Ziegler (Springer, 1999). The idea behind the proof was given by Christian Goldbach (1690–1764), who is best known for his conjecture that there are an inﬁnite number of twin primes, that is, prime numbers that are two apart such as 17 and 19.

22 See The Man Who Loved Only Numbers by Paul Hoffman published by Little Brown and Company in 1999 — a wonderfully readable and interesting book.