## Infinitely many primes via Fermat Numbers

Standard proof of infinitude of prime numbers (due to Euclid) goes as follows:

Assume, to the contrary, that there were only finitely many primes, say $p_1, p_2, ..., p_k$ are all of them. Then, consider the number $N=p_1p_2\cdots p_k+1$. We ask whether $N$ is prime or not. Well, since $N$ is strictly bigger than all of the numbers $p_1,p_2,...,p_k$, by assumption $N$ cannot be prime (because all the primes are assumed to be $p_1,p_2,...,p_k$). So $N$ must be composite. But then a prime factor of $N$ must be $p_j$ for some $j$ with $1\le j\le k$. Now observe that $p_j$ divides both $N$ and $p_1p_2\cdots p_k$, and so divides the difference $N-p_1p_2\cdots p_k=1$. We have shown that $p_j$ divides 1, and this is clearly a contradiction (because every prime is strictly larger than 1).

Let’s show another proof of infinitude of prime numbers using Fermat Numbers. For each $n\in\mathbb{N}$ we define $F_n=2^{2^{n}}+1$. We call $F_n$ the n-th Fermat number. The idea is to show any two Fermat numbers are pairwise relatively prime. Why would this show infinitude of primes? Because if two numbers are pairwise relatively prime, they have distinct prime factors. And since there are infinitely many Fermat numbers, if every pair of them were relatively prime, then clearly we would generate infinitely many primes.

So it remains to show that $\gcd (F_n, F_m)=1$ for every $m,n\in\mathbb{N}$ with $m>n$. Let $d=\gcd (F_m, F_n)$. Observe that

$\displaystyle F_m - 2 = 2^{2^{m}}-1=(2^{2^{n+1}})^{2^{m-n-1}}-1$

Using the factorization $x^q-1=(x-1)(x^{q-1}+x^{q-2}+\cdots +x+1)$, we know $x-1$ divides $x^q-1$. So the above equation implies that $2^{2^{n+1}}-1$ divides $F_m-2$. On the other hand, we have

$\displaystyle 2^{2^{n+1}}-1=(2^{2^{n}}-1)(2^{2^{n}}+1)=(2^{2^{n}}-1)F_n$

Thus, $F_n$ divides $2^{2^{n+1}}-1$. But $2^{2^{n+1}}-1$ divides $F_m-2$. Thus, $F_n$ divides $F_m-2$. By definition of $\gcd$, we know $d$ divides $F_n$, and $F_m$. Since $F_n$ divides $F_m-2$, it follows that $d$ also divides $F_m-2$. But then $d$ divides the difference $F_m-(F_m-2)=2$. We have shown that $d$ divides $2$. Since Fermat numbers are odd, their greatest common divisor must also be odd, hence $d$ is odd. We conclude that $d=1$. This precisely shows that $\gcd(F_n,F_m)=1$, as desired.