# 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

\begin{aligned} \rho = \sum _ {i _ 1,\ldots, i _ n = 0} ^ {\infty} \frac{1}{p _ 1 ^ {i _ 1} \cdots p _ n ^ {i _ n}} = \prod _ {k=1} ^ n \frac{1}{1 - p _ k ^{-1}}. \end{aligned}

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

\begin{aligned} \sum _ {i _ 1 , \ldots , i _ n \leq \lceil \rho \rceil } \frac{1}{p _ 1 ^ {i _ 1} \cdots p _ n ^ {i _ n}} < \rho < \sum _ {m \leq \exp ( \lceil \rho \rceil )} \frac{1}{m} \end{aligned}

where $$\lceil \rho \rceil$$ is the ceiling of $$\rho$$.

Finally define the following sets

\begin{aligned} S &= \{1,2, .. \lceil \exp (\lceil \rho \rceil) \rceil\} \\ S^{\prime} &= \{ p _ 1 ^ {i _ 1} \cdots p _ n ^{i _ n} \mid i _ 1 , \ldots , i _ n = 0,\ldots, \lceil \rho \rceil \} \end{aligned}

and observe that the previous inequality can be rewritten as

\begin{aligned} \sum _ { m \in S ^ {\prime}} \frac{1}{m} < \rho < \sum _ {m \in S} \frac{1}{m} \end{aligned}

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.