# How does the fact that Fermat primes are relatively prime imply there are infinite primes?

I was just reading a book called Proofs from the Book. It presented the proof given by George Polya to prove that two Fermat primes (numbers of the form $2^{2^n} + 1$) are always relatively prime, which in itself is a very elegant proof. But, to say that it implies there are infinitely many primes does not make sense to me.

15 and 16 are relatively prime but it doesn't imply there are infinitely many primes.

• It's important to note that any two Fermat numbers are relatively prime. Fermat primes are specific Fermat numbers, but Fermat numbers are the important concept. – Mark Feb 6 '16 at 8:10
• What is a Fermat number ? Like, what is the difference ? – user230452 Feb 6 '16 at 8:54
• A Fermat number is any positive integer of the form $2^{2^n}}+1$ for a natural number $n$. Not all of these are prime numbers. The ones that are prime are called Fermat primes. – Mark Feb 6 '16 at 8:56

Any sequence $F_n$ of pairwise coprime integers will contain infinitely many primes, because each new $F_n$ has a new prime factor, for all $n\in \mathbb{N}$. In your example, $n=15,16$, but we have infinitely many $n$.

• Wonderful ! I just had an Aha moment ! You're saying that there are an infinite number of Fermat numbers and since they are all pair wise relatively prime, they must all have new prime factors implying there are infinitely many primes. – user230452 Feb 6 '16 at 8:56
• Thanks for the insight. I wasn't able to make that leap in between that sequence and infinite primes. – user230452 Feb 6 '16 at 8:57

Let $M_n=2^n-1$ be the $n$th Mersenne number, and $F_n=2^{2^n}+1$ be the $n$th Fermat number.

$$M_{2^{n}}=2^{2^{n}}-1=\prod_{k=0}^{n-1}(2^{2^{k}}+1)=\prod_{k=0}^{n-1}F_{k}.\tag{1}$$ Hence $$F_{n}=\frac{M_{2^{n+1}}}{M_{2^{n}}}=\frac{\sum_{k=0}^{2^{n+1}-1}2^k}{\sum_{k=0}^{2^{n}-1}2^k} =\frac{\sum_{k=0}^{M_{n+1}}2^k}{\sum_{k=0}^{M_{n}}2^k}=\frac{2^{2^{n+1}}-1}{2^{2^{n}}-1}=2^{2^{n}}+1.\tag{2}$$

As $2$ is prime, Mersenne numbers $M_{2^k}$, with a subscript a power of $2$ only inherit factors from those preceding Mersenne numbers $M_{2^{k-j}}$ subscripts being a lesser power of $2$, $1\leqslant j\leqslant k-1$. These inherited factors are seen to be the Fermat numbers using (1):

\begin{align*} M_{2}&=F_{0}=(2^{2^{0}}+1)\\ M_{4}&=F_{0}F_{1}=(2^{2^{0}}+1)(2^{2^{1}}+1)\\ M_{8}&=F_{0}F_{1}F_{2}=(2^{2^{0}}+1)(2^{2^{1}}+1)(2^{2^{2}}+1)\tag{3}\\ M_{16}&=F_{0}F_{1}F_{2}F_{3}=(2^{2^{0}}+1)(2^{2^{1}}+1)(2^{2^{2}}+1)(2^{2^{3}}+1)\\ M_{32}&=F_{0}F_{1}F_{2}F_{3}F_{4}=(2^{2^{0}}+1)(2^{2^{1}}+1)(2^{2^{2}}+1)(2^{2^{3}}+1)(2^{2^{4}}+1) \end{align*} As such the $M_{2^n}$s primitive prime factors (meaning prime factors not appearing as factors before in the sequence of Mersenne numbers) are the factors of the $(n-1)$th Fermat number, the primitive prime factors in bold being factors of Fermat numbers: \begin{align*} M_{2}&=\mathbf{3}\\ M_{4}&=3\cdot\mathbf{5}\\ M_{8}&=3\cdot5\cdot\mathbf{17}\\ M_{16}&=3\cdot5\cdot17\cdot\mathbf{257}\tag{4}\\ M_{32}&=3\cdot5\cdot17\cdot257\cdot\mathbf{65537}\\ M_{64}&=3\cdot5\cdot17\cdot257\cdot\mathbf{641}\cdot65537\cdot\mathbf{6700417} \end{align*}

Theorem: Fermat numbers are pairwise coprime.

Proof: As $2$ is prime $M_{2^k}\mid M_{2^{k+1}}$ and $M_{2^{k+1}}/M_{2^{k}}$ is an integer being a product of $M_{2^{k+1}}$s primitive factors, hence

$$\gcd(F_{k},F_{k+1}) =\gcd\left(\frac{M_{2^{k+1}}}{M_{2^{k}}},\frac{M_{2^{k+2}}}{M_{2^{k+1}}}\right)=1,$$

is the greatest common divisor of adjacent Fermat numbers is that of the primitive prime factors of $M_{2^{k+1}}$ and $M_{2^{k+2}}$ which is necessarily $1$. It follows the Fermat numbers will be pairwise relatively prime as for any $k$, $j$ $\in\Bbb{N}$,

$$\gcd(F_{k},F_{j})=\gcd\left(\frac{M_{2^{k+1}}}{M_{2^{k}}},\frac{M_{2^{j+1}}}{M_{2^{j}}}\right)=1,$$

where $\gcd(F_{k},F_{j})$ is the greatest common divisor of the primitive prime factors of $M_{2^{k+1}}$ and $M_{2^{j+1}}$.

Q.E.D.

As the Fermat numbers are pairwise coprime this proves the infinitude of primes as each $F_n$ is a product of distinct primes, these being the primitive factors of the Mersenne numbers $M_{2^{n+1}}$, as illustrated by (2), (3), and (4).