Primes using Fermat numbers

Define the nth Fermat number, F_n, by $F_n =2^{2^n}+1$ for n = 0, 1, 2, 3, …. The first few Fermat numbers are F0 = 3, F1 = 5, F2 = 17, F3 = 257.

Prove by induction that F0 ⋅ F1⋯Fn-1 + 2 = Fn, for n ≥ 1.

Proof by induction on $n\ge1$.

---

Base case ($n=1$)

We must check that

$$ F_0 + 2 = F_1. $$

Since $F_0 = 2^{2^0}+1 = 2+1 = 3$ and $F_1 = 2^{2^1}+1 = 4+1 = 5$, we have

$$ F_0 + 2 = 3 + 2 = 5 = F_1, $$

so the statement holds for $n=1$.

---

Inductive step

Inductive hypothesis. Suppose for some $k\ge1$ that

$$ F_0 \,F_1 \,\cdots\, F_{k-1} \;+\; 2 \;=\; F_k. $$

Equivalently,

$$ F_0 F_1 \cdots F_{k-1} \;=\; F_k \;-\; 2. $$

We must show

$$ F_0 F_1 \cdots F_{k-1}\,F_k \;+\; 2 \;=\; F_{k+1}. $$

Starting from the left‐hand side,

$$ F_0 F_1 \cdots F_{k-1}\,F_k \;+\; 2 \;=\;\bigl(F_k - 2\bigr)\,F_k \;+\; 2 \quad(\text{by the inductive hypothesis}). $$

Compute

$$ (F_k - 2)\,F_k =F_k^2 \;-\;2\,F_k =\bigl(2^{2^k}+1\bigr)^2 \;-\;2\bigl(2^{2^k}+1\bigr). $$

Expand:

$$ \bigl(2^{2^k}+1\bigr)^2 =2^{2\cdot2^k} \;+\;2\cdot2^{2^k}\;+\;1 =2^{2^{\,k+1}} \;+\;2^{2^k+1}\;+\;1, $$

so

$$ F_k^2 -2F_k =\bigl(2^{2^{k+1}} +2^{2^k+1}+1\bigr) \;-\;\bigl(2^{2^k+1}+2\bigr) =2^{2^{k+1}} \;-\;1. $$

Thus

$$ F_0 F_1 \cdots F_{k-1}\,F_k +2 =\bigl(F_k^2 -2F_k\bigr)+2 =\bigl(2^{2^{k+1}} -1\bigr)+2 =2^{2^{k+1}}+1 =F_{k+1}. $$

This completes the inductive step.

---

By the principle of mathematical induction, for every integer $n\ge1$,

$$ F_0\,F_1\cdots F_{n-1} +2 \;=\; F_n, $$

as claimed. ∎

Use this formula to prove that there are an infinite number of primes, by showing that no two Fermat numbers have any prime factors in common.

Here’s the standard argument.

---

1. Fermat numbers are pairwise coprime

Recall from the induction you’ve already proved that, for every $n\ge1$,

$$ F_n \;=\; F_0\,F_1\cdots F_{n-1} \;+\;2. $$

Fix two indices $0\le m<n$. Suppose $p$ is a prime dividing both $F_m$ and $F_n$. Then:

1. Since $p\mid F_n$ and

   $$ F_n = F_0F_1\cdots F_{n-1} +2, $$

   we have

   $$ F_0F_1\cdots F_{n-1} \;+\;2 \;\equiv\;0\pmod p \quad\Longrightarrow\quad F_0F_1\cdots F_{n-1}\;\equiv\;-2\pmod p. $$

2. But $p\mid F_m$ for some $m<n$, so $p$ divides the product $F_0F_1\cdots F_{n-1}$. Hence

   $$ F_0F_1\cdots F_{n-1}\;\equiv\;0\pmod p. $$

3. Combining the two congruences,

   $$ 0 \;\equiv\; F_0\cdots F_{n-1}\;\equiv\;-2\pmod p \quad\Longrightarrow\quad p\mid2. $$

   Thus $p=2$. But every Fermat number $F_k = 2^{2^k}+1$ is odd, so cannot be divisible by 2.

Therefore no prime $p$ can divide both $F_m$ and $F_n$ for $m<n$. Equivalently,

$$ \gcd(F_m,\,F_n)\;=\;1 \quad\text{whenever }m\neq n. $$

---

2. Infinitely many primes

Since each Fermat number $F_n$ is greater than 1, it has at least one prime divisor. By the argument above, no prime divisor of $F_n$ can ever appear among the prime divisors of any other $F_m$ with $m\neq n$. Hence each $F_n$ contributes at least one new prime that we have never seen before. As $n$ ranges over the nonnegative integers, we thus get infinitely many distinct primes. ∎