Year: 2002
Paper: 2
Question Number: 3
Course: LFM Pure
Section: Proof by induction
Difficulty Rating: 1600.0
Difficulty Comparisons: 0
Banger Rating: 1552.5
Banger Comparisons: 3
The $n$th Fermat number, $F_n$, is defined by
\[
F_n = 2^{2^n} +1\, ,
\ \ \ \ \ \ \ n=0, \ 1, \ 2, \ \ldots \ ,
\]
where $\ds 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_0F_1 \ldots F_{k-1} = F_k-2 \;. \tag{*}
$$
Prove, by induction, or otherwise, that
$(*)$ holds for all $k\ge1$. Deduce that no two Fermat numbers
have a common factor greater than $1$.
Hence
show that there are infinitely many prime numbers.
\begin{align*}
&& F_0 &= 2^{2^0}+1 \\
&&&= 2^1+1 = 3\\
&& F_1 &= 2^{2^1}+1 \\
&&&= 2^2+1 = 5 \\
&& F_2 &= 2^{2^2}+1 \\
&&&= 2^4+1 \\
&&&= 17 \\
&&F_3 &= 2^{2^3}+1 \\
&&&= 2^8+1 \\
&&&= 257 \\
\\
&& \text{empty product} &= 1\\
&& F_1 - 2 &= 3-2 = 1\\
\Rightarrow&& 1 &= F_1-2\\
&& F_0 &=3 \\
&& F_2-2 &= 3 \\
\Rightarrow && F_0 &= F_2 - 2\\
&& F_0F_1 &= 3 \cdot 5 = 15 \\
&& F_3-2 &= 17-2 = 15 \\
\Rightarrow && F_0F_1 &= F_3-2
\end{align*}
\begin{align*}
&& F_0 F_1 \cdots F_{k-1} &= \prod_{i=0}^{k-1} \left ( 2^{2^{i}}+1\right) \\
&&&= \sum_{l = \text{sum of }2^i} 2^l \\
&&&= \sum_{l=0}^{2^{k}-1}2^l \\
&&&= 2^{2^k}-1 \\
&&&= F_k-2
\end{align*}
Suppose $p \mid F_a, F_b$ with $b > a$, then $p \mid 2=F_b - F_0\cdots F_a \cdots F_{b-1}$ therefore $p = 1, 2$, but $2 \nmid F_a$ for any $a$. Therefore any number dividing two Fermat numbers is $1$, ie they are all coprime.
Consider the smallest prime dividing $F_n$ for each $n$. Clearly these are all different since each $F_n$ is coprime from all the others. Clearly there are infinitely many of time (since there are infinitely many $F_n$). Therefore there are infinitely many primes.