# 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 natural numbers, 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 TheoremThere 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.

#### Contents

## Euclid's Proof

For any finite set of primes \(\{p_1, p_2, p_3, \cdots, 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 can not be the collection of

allprime numbers. \(_\square\)Notice that Euclid's original proof was a direct proof, not a proof by contradiction.

## Euler's Proof

Euler started his proof by assuming that there are only finitely many primes \(p_1, p_2, p_3, \cdots, 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.\]

\((2)\) is the infamous harmonic series and it diverges.

This is a contradiction!

So, there

be finitely many primes. \(_\square\)cannot

## Proof using Fermat numbers

For this proof, we need to know what

Fermat numbersare. 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{align} \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{align}\]

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\mid2\). 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\)

## Idea similar to the proof using Fermat numbers

It is enough to find an infinite sequence of natural numbers \(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, \cdots ,\) 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 natural numbers. 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\)

## Thue's Proof

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\)

## Proof based on information theory

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} \ldots 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.

## Fürstenberg's topological proof

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.

## Largest known prime number

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^{74,207,281} - 1\), having 22,338,618 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 49 are known so far, the largest of which is the above.

**Cite as:**Infinitely Many Primes.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/infinitely-many-primes/