Using Fermat Number to prove the infinity of primes

April 19, 2020 | 2 min read

What is Fermat Number?

Fermat number is defined as $2^{2^n}+1$ (named after Pierre de Fermat) where $n$ is a non-negative integer. The first five Fermat numbers are $3, 5, 17, 257$ and $65537$. We denote $F(n) = 2^{2^n}+1$ for convenience. So,

Lemma 1: $F(m)−2$ is divisible by $F(n)$ if $m > n$.

Proof:

$F(m)−2$ $= 2^{2^m}−1$ $= ({2^{2^{m−1}}+1})×({2^{2^{m−1}}−1})$ $=F(m−1)×\Big(F(m−1)−2\Big)$

Similarly, $F(m−1)−2 = F(m−2)×\Big(F(m−2)−2\Big)$. Hence, we can deduce that

So, $F(m)−2$ is divisible by $F(n)$ if $m > n$.

Lemma 2: $F(m)$ and $F(n)$ are relatively prime if $m \ne n$. (That means their greatest common divisor is $1$)

Proof:

Assume $m > n$, and let $g$ be the greatest common divisor of $F(m)$ and $F(n)$. So, $g|F(m)$ and $g|F(n)$

($g|F(m)$ means $g$ divides $F(m)$ OR $F(m)$ is divisible by $g$)

The fact that $g|F(n)$ and by lemma 1, $F(n)|\Big(F(m)−2\Big)$, $g|\Big(F(m)−2\Big)$ So, $g|\bigg(F(m)−\Big(F(m)−2\Big)\bigg)$ and thus $g|2$ i.e. $g = 1$ or $2$ But all Fermat numbers are odd, therefore $g$ must be $1$. Hence, $F(m)$ and $F(n)$ are relatively prime if $m$ is not equal to $n$.

Final deduction

Now, to prove the infinity of primes, we keep generating Fermat numbers $F(n)$. If $F(n)$ is prime, we have a new prime number. If $F(n)$ is composite, then it has a prime factor which never exists before since all distinct Fermat numbers are relatively prime (by lemma 2). As we can generate as many Fermat numbers as we want by simply substituting different values of $n$, so the number of primes is infinite.

Written by Danny Siu who lives in Hong Kong. You should follow him on Twitter

• ← SVD and basis
• How to build multiple counters using React and Redux →