In a recent post I showed that there are infinitely many prime numbers. A little stronger fact than this is that the sum of the reciprocals of prime numbers diverges, which I attempted to concisely explain in this Quora response. I have always wanted to find a simple proof of this fact, but so far I have not been successful. Euler’s proof to date appears to me to be the most straightforward argument. However at the time of writing this post, this Wikipedia entry lists Euler’s proof and calls its steps *a sequence of audacious leaps of logic.*

While I think most mathematicians looking at this “proof” today would agree it is not a sound argument, it is also very clear how to remove the troublesome “leaps of logic,” leaving behind a correct proof. Given how straightforward it is to correct, I would personally hesitate in criticising Euler’s methods and assume that he *meant* the correct things but just used a notation and language which is imprecise by today’s standards. In any case I provide below a reconstruction of Euler’s proof, with my own added details to make it a rigorous argument.

In what follows \(p _ 1, p _ 2, \ldots \) will be the sequence of prime numbers, and I will make free use of the following series formula:

For \( x > 1 \) we have

\[ \sum _ {k = 0} ^{\infty} \frac{1}{x^k} = \frac{1}{1-x^{-1}} \]

For \( x > 1 \) we have

\[\ln \frac{1}{1-x^{-1}} = \sum _ {k = 0}^{\infty} \frac{1}{kx^k}\]

Also as in my previous post about infinitude of primes I make use of the following key fact about prime numbers

Suppose that \(j > 1\) is a positive integer. Then there exists prime numbers \(p _ 1,p _ 2,\ldots,p _ n\) and integers \(i _ 1, i _ 2, \ldots , i _ n \) such that \(j=p _ 1 ^ {i _ 1} p _ 2 ^ {i _ 2} \cdots p _ n ^ {i _ n}\).

I will need a bound on the partial sums of the harmonic series, as I will use this as a comparison to prove divergence. The following bound is crude, but captures the right asymptotics for a helpful comparison.

Suppose that \( n \) is a positive integer. Then by prime factorization and the geometric sum formula above the following inequality holds

$$ \begin{aligned} \sum _ {j=1}^{n} \frac{1}{j} &\leq \prod _ {j=1}^n \sum _ {k = 0} ^ {n} \frac{1}{p _ j ^k } \\ &\leq \prod _ {j=1}^n \sum _ {k = 0} ^ {\infty} \frac{1}{p _ j ^k } \\ &= \prod _ {j=1}^n \frac{1}{1-p _ j ^{-1}}. \end{aligned} $$

Therefore, since the function \(\ln\) is strictly increasing we have for any positive integer \(n:\)

$$ \begin{aligned} \ln \sum _ {j=1}^{n} \frac{1}{j} &\leq \ln \prod _ {j=1}^{n}\frac{1}{1-p _ j^{-1}}\\ &= \sum _ {j=1} ^ {n} \ln \frac{1}{1 - p _ j ^{-1}}\\ &= \sum _ {j=1}^{n} \sum _ {k=1} ^ {\infty} \frac{1}{kp _ j ^k} \\ &= \sum _ {j=1}^{n}\frac{1}{p _ j} + \sum _ {j=1}^{n} \sum _ {k=2} ^ {\infty} \frac{1}{kp _ j ^k} \\ &< \sum _ {j=1}^{n}\frac{1}{p _ j} + \sum _ {j=1}^{n} \sum _ {k=2} ^ {\infty} \frac{1}{p _ j ^k} \\ &= \sum _ {j=1}^{n}\frac{1}{p _ j} + \sum _ {j=1}^{n} \frac{p _ j ^{-2}}{1 - p _ j ^{-1}} \\ &< \sum _ {j=1}^{n}\frac{1}{p _ j} + \sum _ {m=2}^{\infty} \frac{1}{m^2 - m} \\ &= \sum _ {j=1}^{n}\frac{1}{p _ j} + 1. \end{aligned} $$

since the left hand side of this inequality tends to \(\infty\) as \(n \to \infty\) we conclude that

$$ \begin{aligned} \lim _ {n \to \infty} \sum _ {j=1}^{n}\frac{1}{p _ j} = \infty \end{aligned} $$

as well.