# 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.