# Infinitely Many Primes

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

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

It's not hard to notice that as numbers get larger, the primes get more and more scarce. So a question arises: is there a point where you find the largest prime and all the numbers that come after that are all composite?

The answer turns out to be no.

Hence the following theorem:

There are infinitely many primes. \(_\square\)

This was first proven by Euclid of Alexandria around \(300\) B.C. We're going to see Euclid's proof here along with a couple of others.

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

## The Current Largest Prime Number

It is hard to find a new primer number. The current largest prime number can be expressed as \( 2^{74,207,281} -1,\) and it has \(22,338,618\) digits and was discovered using a program called GIMPS or Great Internet Mersenne Prime Search. (http://www.mersenne.org/)

The program works by having users all over the world download a program which will test different numbers for \(2^x -1.\) A central computer assigns the local computer a number for \(x\) to test, and once the local computer finishes, it reports it back to the server. It is very rare to find a prime number, and only 49 different Mersenne primes have been found despite over 1 million computers working on the project.

To learn more about how the software works, go here.

A Mersenne prime is a prime number that can be expressed in the form \(2^x -1,\) where \(x\) is a prime number. (If \(x\) was not prime, then it would not be prime.)

Note: This section is still in progress and will be completed shortly.

**Cite as:**Infinitely Many Primes.

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