2002 Paper 2 Q3

Year: 2002
Paper: 2
Question Number: 3

Course: LFM Pure
Section: Proof by induction

Difficulty: 1600.0 Banger: 1552.5

Problem

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.

Solution

\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.
Rating Information

Difficulty Rating: 1600.0

Difficulty Comparisons: 0

Banger Rating: 1552.5

Banger Comparisons: 3

Show LaTeX source
Problem source
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.
Solution source
\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.