Euclid’s Proof of the Infinity of Primes

UPDATE: The initial version of this article presented Euclid’s proof as a proof by contradiction. While the proof was valid, it included an unnecessary step and did not precisely reflect Euclid's original argument. This historical inaccuracy was noted by Michael Hardy; see the first response in this article. I am grateful to him for highlighting this error. The proof has since been revised to present a direct approach, aligning more closely with Euclid's original method.

Let us suppose we have a finite collection P of distinct prime numbers:

Next, we consider the following natural number m:

This number m will have a prime divisor; let's denote this prime divisor as p. A crucial observation is as follows:

Suppose, for contradiction, that this is not true. This implies that p divides both m and the product of all primes. Formally, we can express this as:

where A and B are positive natural numbers satisfying A > B. If we take the difference, we derive:

Note that the difference A-B is a positive natural number. Consequently, for the equation to hold, we must have:

Given that we assumed p is a prime divisor, we reach a contradiction, confirming that our earlier observation is indeed correct, namely that:

This indicates that p is a prime number not included in the set P. Therefore, any finite set of primes P can always be augmented by adding a prime that is distinct from all primes within P. We conclude that no finite collection of primes can encompass all prime numbers. The theorem is proven!

Erd?s’s Proof of the Infinity of Primes

Erd?s's proof actually establishes a significantly stronger result: if P represents the entirety of prime numbers, then the following series diverges:

To clarify, a series is deemed convergent if the sequence of its partial sums approaches a limit L, which is a real number. Formally, this can be stated as:

If a series does not converge, it is termed divergent. A key observation here is that if a series is divergent, it must contain infinitely many non-zero terms, which we will utilize in our proof. However, it’s important to note that the converse is not universally applicable; a series may contain infinitely many non-zero terms but still converge (e.g., geometric series).

To summarize, the proof's outline is as follows: we will examine the sum of the reciprocals of prime numbers and demonstrate that this sum diverges. This implies that the number of non-zero terms must be infinite; otherwise, the sum would be finite. Thus, we will conclude there are infinitely many primes! Before we proceed, it is worth mentioning that the divergence of the sum of the reciprocals of prime numbers was first established by Euler in 1737; further details can be found here. However, the proof we will present was formulated by Paul Erd?s.

Once again, we will employ a proof by contradiction. We define the sequence of prime numbers in ascending order:

Let's assume that the sum of their reciprocals converges to some positive real number L, which means that:

If you are concerned that by stating this we have implicitly assumed the infinitude of primes (since the summation is infinite), let me clarify that there is no issue. We can define the sum as the summation of the reciprocals of all primes, and if we exhaust the terms, we can simply replace the “non-existent” terms with zeros, ensuring that the summation remains unaffected. In other words, we slightly stretch the notation and use infinite summation notation, even if the actual summation is finite.

Next, we apply the definition of convergence of the sequence of partial sums. From our previous discussion, we have:

Since the sequence of partial sums converges, by employing the formal definition of convergence, we can conclude that there exists a natural number k such that:

Let us define N as follows:

We will categorize all natural numbers from 1 to N into two groups:

• Numbers divisible by at least one large prime (let's denote the count as N(b)).
• Numbers that are divisible only by small primes (let's denote the count as N(s)).

Notably, by definition, we have that N(b) + N(s) = N. We will now attempt to estimate N(b) and N(s).

Starting with N(b), we want to tally all natural numbers from 1 to N that are divisible by at least one large prime. For any prime number p, the count of positive natural numbers less than or equal to N that are multiples of p is at most N / p. Thus,

The last inequality stems from the definition of k.

Next, we turn our attention to N(s). We can express every number n ? N that has only small prime divisors as follows:

It is noteworthy that any natural number can be expressed in this manner. This implies that since n consists solely of small prime divisors, the term a represents a product of distinct small primes. Given that there are k small primes, this means there are 2^k different square-free parts. Furthermore, since n ? N, we find:

This leads us to conclude that there are at most sqrt(N) distinct square parts. Combining these observations, we deduce:

Our two upper bounds for N(b) and N(s) now yield:

This leads to a contradiction, as we must have N(b) + N(s) = N. Thus, the proof is complete!

Note: The article contains Amazon Affiliate links.

References

• “Proofs from THE BOOK” by Martin Aigner and Günter M. Ziegler. Springer.
• https://en.wikipedia.org/wiki/Euclid%27s_theorem
• https://en.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes