Infinitely Many Primes

A prime number is a positive integer that has exactly 2 positive divisors. The first few prime numbers are

$$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \ldots.$$

When we go to larger positive integers, we notice that prime numbers get more and more scarce. Is it possible that at some point, we have found all the prime numbers and thus everything larger is composite? The answer turns out to be no:

Euclid's Theorem

There are infinitely many primes.

There have been many proofs of this fact. The earliest, which gave rise to the name, was by Euclid of Alexandria in around 300 B.C. This page lists several proofs of this theorem.

For any finite set of primes $\{p_1, p_2, p_3, \ldots, p_n\}$, Euclid considered the number

$$n=p_1p_2p_3\cdots p_n +1.$$

$n$ has a prime divisor $p$ (every integer has at least one prime divisor). But $p$ is not equal to any of the $p_i.$ $($If $p$ were equal to any of the $p_i$, then $p$ would have to divide $1$, which is impossible.$)$ So for any finite set of prime numbers, it is possible to find another prime that is not in that set.

In other words, a finite set of primes cannot be the collection of all prime numbers. $_\square$

Notice that Euclid's original proof was a direct proof, not a proof by contradiction.

Euler started his proof by assuming that there are only finitely many primes $p_1, p_2, p_3, \ldots, p_n$. Then he considered

$$N=\prod_{i=1}^n \left(1+\frac{1}{p_i}+\frac{1}{{p_i}^2}+\cdots+ \frac{1}{{p_i}^k}+\cdots\right)=\prod_{i=1}^n\dfrac{1}{1-\frac{1}{p_i}}. \qquad (1)$$

On the other hand, expanding the product and using the fact that every integer can be uniquely expressed as a product of primes, we get

$$N=1+\frac{1}{2}+\frac{1}{3}+\cdots. \qquad (2)$$

It is apparent that $(1)$ converges. Here, we have used the formula for the infinite geometric series:

$$1+x+x^2+x^3+\cdots=\dfrac{1}{1-x} \text{ for } |x|<1.$$

Note that $(2)$ is the infamous harmonic series and it diverges, which is a contradiction!

So, there cannot be finitely many primes. $_\square$

This is a relatively new proof that was first published in 2005. Unlike the last two proofs, which rely on contradiction, this proof makes use of induction.

First, take any number $n$. For simplicity, we can just say that it's prime. As in Euclid's proof, we can add $1$ to $n$ to get a new number, $n+1$. These two integers must be coprime* and thus their product has at least two different prime factors. Now take $m = n(n+1)$, which we know has two prime factors, and repeat this process:

$$m = n(n+1),\quad m +1= n(n+1) +1.$$

$m$ and $m+1$ must likewise be coprime and thus have at least three different prime factors. This can be continued indefinitely. $_\square$

* Take $n$ and $n+1.$ Assume that there is a factor $d$ which divides $n$ and let $\frac nd =s.$ Dividing $n+1$ by $d$ gives us $s + \frac1d,$ which cannot hold for integers unless $d=1,$ in which case $d$ is just a trivial factor. Thus, the greatest common divisor between these two numbers is $1$, making them coprime.

For this proof, we need to know what Fermat numbers are. Fermat numbers $F_n$ are of the form $2^{2^n}+1,$ where $n$ is a non-negative integer. The first few Fermat numbers are $3, 5, 17, 257, 65537$.

We'll prove that any two Fermat numbers are relatively prime. Since there are an infinite number of Fermat numbers, this will prove that there are an infinite number of primes.

Take a look at the following relation:

$$\displaystyle\prod_{i=0}^{n-1} F_i=F_{n}-2. \qquad (1)$$

This is not hard to prove using induction. For $n=1$, we have $F_0=3$ and $F_1-2=3$. So $(1)$ is true for $n=1$.

Assume that it is true for any $n$. Then

$$\begin{aligned} \prod_{i=0}^{n-1} F_i \times F_n &=(F_n-2)F_n\\ &=\left(2^{2^n}-1\right)\left(2^{2^n}+1\right)\\ &=2^{2^{n+1}}-1\\ &=F_{n+1}-2. \end{aligned}$$

So, $(1)$ is true for all positive integers $n$.

We're actually done proving that any two Fermat numbers are co-prime since if $F_i$ and $F_n$ (with $i<n$) have a common factor $k$, then from $(1)$, $k\, \big| \, 2$. This means $k$ equals either $1$ or $2$. But $k$ cannot be equal to $2$ since all Fermat numbers are odd. That means $k=1$ and $F_i$ and $F_n$ are co-prime.

From that we can say there are infinitely many primes. $_\square$

It is enough to find an infinite sequence of positive integers $1 < a_1 < a_2 < a_3 < \cdots$ that are pairwise relatively prime (i.e. without a common prime factor). So, if $p_1$ is a prime dividing $a_1$, if $p_2$ is a prime dividing $a_2$, etc., then $p_1, p_2, \ldots ,$ are all different.

If $S_0$ and $a$ are relatively prime integers with $S_0 > a \geq 1$, the sequence defined by the recursive relation

$$S_n - a = S_{n-1}\left(S_{n-1} - a\right) ~\text{ for } n \geq 1$$

consists of pairwise relatively prime positive integers. In the best situation, i.e. when $S_0 = 3$ and $a = 2$, the sequence is in fact the sequence of Fermat numbers: $S_n = F_n = 2^{2^{n}} + 1$.

Similarly, if $S_0$ is odd and

$$S_n = (S_{n -1})^{2} - 2 ~\text{ for } n \geq 1,$$

then again the integers $S_n$ are pairwise relatively prime. $_\square$

Let $n,k \geq 1$ be integers such that $(1+n)^{k} < 2^{n},$ and let $p_{1} = 2, p_{2} = 3, \cdots , p_{r}$ be primes satisfying $p_{i} < 2^{n}$. Suppose that $r \leq k$.

Then by the fundamental theorem, every integer $m$ such that $1 \leq m \leq 2n$ may be written in a unique way in the form

$$m = 2^{e_1} · 3^{e_2} \cdots p^{e_r},$$

where $0 \leq e_{1} \leq n, ~0 \leq e_{2} < n, ~\cdots , ~0 \leq e_{r} < n$. Counting all the possibilities, it follows that

$$2^{n} \leq (n + 1)n^{r-1} <(n + 1)^{r} \leq (n + 1)^{k} < 2^{n},$$

and this is absurd. So $r \geq k + 1$.

Choose $n = 2k^{2}$. From $1 + 2k^{2} < 2^{2k}$ for every $k \geq 1$, it follows that $\left(1 + 2k^{2}\right)^{k} ≤ 2^{2k^{2}} = 4^{k^{2}}$.

Thus, there exist at least $k + 1$ primes $p$ such that $p < 4^{k^{2}}$ . Since $k$ may be taken arbitrarily large, this shows that there are infinitely many primes. $_\square$

Suppose there are finitely many prime numbers, $p_1, p_2, p_3, \ldots, p_k$. By fundamental theorem of arithmetic, each positive integer $n$ can be represented uniquely as $n = p_1^{e_1} p_2^{e_2} p_3^{e_3} \cdots p_k^{e_k},$ where $e_1, e_2, e_3, \ldots, e_k$ are nonnegative integers. Denote the mapping $f : \mathbb{N} \to \mathbb{N}_0^k$ mapping $n$ to $(e_1, e_2, e_3, \ldots, e_k)$. Note that $f$ is clearly a bijection.

Note that since $p_i \ge 2, e_i \ge 0$, we have $p_i^{e_i} \ge 1$ for all $i$, and thus $p_i^{e_i} \le n$ for all $i$. Thus $e_i \le \log_{p_i} n \le \log_2 n$. Thus if we fix some large $N$ and let $n \le N$, all components of $f(n)$ must be at most $\log_2 n \le \log_2 N$. Thus among $f(1), f(2), f(3), \ldots, f(N)$, there are at most $(\log_2 N)^k$ distinct values. But since $f$ is bijective, we need $N$ distinct values. Thus we need $(\log_2 N)^k \ge N$. This is clearly false for large enough $N$. So there are infinitely many prime numbers. $_\square$

On the set of integers $\mathbb{Z}$, define a topology having subbase of all non-constant arithmetic progressions (unbounded in both directions). It can be shown that all open sets in this topology are either infinite or empty.

For each prime $p$ and integer $k$, define $A_{p,k}$ to be the set of all integers in the arithmetic progression with difference $p$, containing $k$. We can easily see that $A_{p,0}$ is precisely the set of all integers divisible by $p$. Moreover, we have $A_{p,1} \cup A_{p,2} \cup \ldots \cup A_{p,p-1} = (A_{p,0})^c$. The left-hand side is the union of open sets and thus open; so $A_{p,0}$ is closed.

Now suppose there are finitely many prime numbers. Then the union $U$ of all $A_{p,0}$, being a finite union of closed sets, is also closed. But by definition of prime numbers, the only integers not divisible by any prime are the units 1 and -1. Thus the complement of $U$ is $\{-1, 1\}$. Being the complement of a closed set, $\{-1, 1\}$ should be open; but this is a finite non-empty set, contradicting our result that open sets in this topology are either infinite or empty. Thus there must be infinitely many prime numbers. $_\square$

Despite there being infinitely many prime numbers, it's actually difficult to find a large one. For recreational purposes, people have been trying to find as large prime number as possible. The current largest known prime number is $2^{82,589,933} - 1$, having 24,862,048 digits. This was found by the Great Internet Mersenne Prime Search project, which uses distributed computing to discover prime numbers in the form $2^n - 1$, known as Mersenne primes. Mersenne primes are very rare; in fact, it's an open problem whether there are infinitely many Mersenne primes or not. Only 50 are known so far, the largest of which is the above.