Review question

# Are any two Fermat numbers relatively prime? Add to your resource collection Remove from your resource collection Add notes to this resource View your notes for this resource

Ref: R8677

## Solution

The Fermat numbers $F_n$ are defined by $F_n=2^{2^n}+1$, $n\in\mathbb{Z}^+$.

Show that, for any positive integer $k$, $F_m$ divides $F_{m+k}-2$, and deduce that any two distinct Fermat numbers are relatively prime.

Using $F_n=2^{2^n}+1$, we’ll write $F_{m+k}-2$ in terms of $F_m$. We have \begin{align*} F_{m+k}-2 &=2^{2^{m+k}}-1 \\ &=\left(2^{2^{m+k-1}}\right)^2-1 \\ &=\left(2^{2^{m+k-1}}-1\right)\times \left(2^{2^{m+k-1}}+1\right) \\ &=\left(2^{2^{m+k-2}}-1\right)\times \left(2^{2^{m+k-2}}+1\right)\times \left(2^{2^{m+k-1}}+1\right) \\ &=\cdots \\ &= F_m\times \left(2^{2^m}+1\right)\times \left(2^{2^{m+1}}+1\right)\times\cdots\times\left(2^{2^{m+k-1}}+1\right) \end{align*}

Therefore, $F_m$ divides $F_{m+k}-2$.

Take any two distinct Fermat numbers, say $F_a < F_b$. Let $d = \gcd(F_a, F_b)$.

The expression $\gcd(a,b)$ stands for ‘the greatest common divisor of $a$ and $b$’, or the ‘highest common factor of $a$ and $b$’.

We know $F_a|F_b-2$ (where the vertical line means ‘divides into exactly’). Using the definition of $d$, $d|F_a$ and, hence, $d|F_b-2$.

Since we also know that $d|F_b$, it follows that $d|F_b-(F_b-2)$, and so $d|2$.

But all Fermat numbers are odd, and, therefore, $d$ cannot be $2$. So $d=1$, and the numbers $F_a$ and $F_b$ are relatively prime.

Deduce that there are at least $n+1$ distinct prime numbers less than or equal to $F_n$, for any $n$

We know that for every $i\in \{0,1,2,...,n-1\}$, $F_i$ and $F_n$ are coprime.

Therefore, working upwards, each $F_i$’s factorisation should contain at least one new prime number smaller than $F_n$.

Justification: Fermat numbers are increasing, and any two Fermat numbers are coprime.

So there are at least $n$ prime numbers less than $F_n$.

But, $F_n$’s factorisation should also contain a new prime, and, obviously, that prime would be less than or equal to $F_n$.

Hence, there are at least $n+1$ distinct prime numbers less than or equal to $F_n$.

… and hence that there are infinitely many prime numbers.

We’ll give a proof by contradiction.

Suppose that there are finitely many prime numbers, say $N$.

Then, if we look at $F_N$, there are at least $N+1$ prime numbers less than or equal to $F_N$, which contradicts our assumption.

Hence, there are infinitely many primes.