Infinitely many prime numbers: Euler's proof

July 04, 2014

(Note: I have updated this post to reflect that the origin of this argument was Euler, although it was unknown to me when I first posted this)

I really enjoy prime numbers and proving facts about them. One of the most basic facts about prime numbers is that there are infinitely many of them. There are many ways to prove this, and it’s fun going through all these proofs to get a different point of view on this basic fact.

Below I give Euler’s proof, which is a novel and interesting proof to me becuase number theory arguments often have a discrete feel to them, but Euler’s argument approaches it from the point of view of elementary analysis.

Lemma 1: Prime Factorization

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

Lemma 2: Divergence of Harmonic Sum

We have \[ \lim _ {m\to\infty} \sum _ {n=1}^m \frac{1}{n} = \infty . \]

Main Fact: There are infinitely many prime numbers.

In order to obtain a contradiction assume that there are at most \(k\) prime numbers. Write these prime numbers as \(p _ 1,p _ 2,\ldots, p _ k \). Then by lemma 1 (and a little thought) we have the following inequality

\[ \sum _ {n=0} ^ m \frac{1}{n} < \sum _ {i _ 1 = 0} ^m \sum _ {i _ 2 = 0} ^ m \ldots \sum _ {i _ k =0} ^m \frac{1}{p _ 1 ^ {i _ 1} p _ 2 ^ {i _ 2} \cdots p _ k ^ {i _ k}}. \]

This however contradicts lemma 2 as the right hand side of this inequality is a geometric sum, and therefore converges as \(m \to \infty \).