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.