Infinitude of Primes Revisited

December 07, 2014

In a previous post I gave a nice proof that there are infinitely many prime numbers. The proof however is somewhat nonconstructive because by way of a contradiction argument I sneak around issues of actually constructing a new prime not in a prespecified finite list, which would be the “constructive” manner of proving this same fact.

I have wondered periodically since then whether it could be possible to adapt a similar argument to a constructive proof. The answer turns out to be yes, and I will present a procedure for this now. Given the first \(n \) prime numbers, the procedure will generate an \(n+1\)th prime number not in this list.

Suppose that \(p _ 1, p _ 2 , \ldots , p _ n \) are the first \(n \) prime numbers, and define

Since the harmonic sum grows logarithmically we have the following strict inequalities:

where \( \lceil \rho \rceil \) is the ceiling of \( \rho \).

Finally define the following sets

and observe that the previous inequality can be rewritten as

Therefore, by unique factorization and the fact that the inequalities are strict, the set \( S \setminus S^{\prime} \) is nonempty and furthermore its least element is a prime number not in the original sequence.