Solution to problem 28

To begin with, we have by direct calculation that $F_0=3$, $F_1=5$, $F_2=17$ 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$ so that

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

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

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<m$. 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 infinitely many Fermat numbers, there must be infinitely 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 first 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 infinitely 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.