In our previous post, we gave three elementary number-theoretic proofs of the infinitude of the prime numbers. Today, in an unforgivably delayed second installment, we provide two proofs using machinery from more distant fields of mathematics: analysis and topology.

A small word of warning: today’s proofs, though not difficult, require a bit more mathematical sophistication than those of the previous post. The first proof will involve some manipulation of infinite sums, and the second proof uses rudiments of topology, which we introduced here.

Without further ado, let us begin. Our first proof today dates to the 18th century and is due to the prolific Leonhard Euler, of whom Pierre-Simon Laplace, an exceptional mathematician in his own right, once said, “Read Euler, read Euler, he is the master of us all.”

Proof Four (Euler): Suppose there are only finitely many prime numbers, $\{p_1, p_2, \ldots, p_n\}$. For each prime number $p$, consider the infinite series $\sum_{i = 0}^\infty \frac{1}{p^i} = 1 + \frac{1}{p} + \frac{1}{p^2} + \ldots$. As you probably learned in a precalculus class, the value of this infinite sum is precisely $\frac{1}{1-\frac{1}{p}}$.

Now recall that every natural number greater than 1 can be written in a unique way as a product of prime numbers. Since $\{p_1, \ldots, p_n\}$ are all of the primes, this means that, for each natural number $m \geq 1$, we can express $\frac{1}{m}$ as $\frac{1}{p_1^{s_1}} \cdot \frac{1}{p_2^{s_2}} \cdot \ldots \cdot \frac{1}{p_n^{s_n}}$ for some natural numbers $s_1, s_2, \ldots, s_n$. Moreover, it is clear that this gives a one-to-one correspondence between natural numbers $m \geq 1$ and the corresponding $n$-tuples of natural numbers, $\langle s_1, s_2, \ldots, s_n \rangle$. Putting this all together, we obtain the following remarkable formula:

$\sum_{m=1}^\infty \frac{1}{m} = \prod_{k=1}^n \frac{1}{1-\frac{1}{p_k}}$.

The sum on the left hand of this equation is the famous harmonic series, and it is well-known and easily verified that this sum diverges to infinity. On the other hand, the product on the right hand is a finite product of finite numbers and is therefore finite! This gives a contradiction and concludes the proof.

Our next proof was published in 1955 by a young Hillel Furstenburg, who is still active at the Einstein Institute of Mathematics here in Jerusalem.

Proof Five (Furstenberg): For all integers $a$ and $b$, let $U_{a,b}$ be the set $\{a + bk \mid k \in \mathbb{Z} \}$, i.e., $U_{a,b}$ contains $a$ and all integers that differ from $a$ by a multiple of $b$.

Claim: For all pairs of integers $(a_0, b_0)$ and $(a_1, b_1)$, either $U_{a_0,b_0} \cap U_{a_1, b_1} = \emptyset$ or there are $a_2, b_2$ such that $U_{a_0,b_0} \cap U_{a_1, b_1} = U_{a_2, b_2}$.

Proof of Claim: If $U_{a_0, b_0} \cap U_{a_1, b_1} \neq \emptyset$, then let $a_2$ be any element of the intersection, and let $b_2$ be the least common multiple of $b_0$ and $b_1$. It is easily verified that $U_{a_0,b_0} \cap U_{a_1, b_1} = U_{a_2, b_2}$, thus finishing the proof of the claim.

It now follows that we can define a topology on $\mathbb{Z}$ by declaring that a set $U \subseteq \mathbb{Z}$ is open if and only if $U = \emptyset$ or $U$ is a union of sets of the form $U_{a,b}$. In particular, for each prime number $p$, the set $U_{0,p}$, which is the set of all multiples of $p$, is open. However, $U_{0,p}$ is also closed, since it is the complement of the set $\bigcup_{0 < a < p} U_{a,p}$, which is an open set.

Now suppose that there are only finitely many prime numbers, $\{p_1, \ldots, p_n\}$. Since each set $U_{0,p_k}$ is closed and a finite union of closed sets is closed, we have that $\bigcup_{k = 1}^n U_{0,p_k}$ is a closed set. Notice that every integer that is not $1$ or $-1$ is a multiple of some prime number, so $\bigcup_{k = 1}^n U_{0,p_k}$ is precisely the set of all integers except $1$ and $-1$. Since it is closed, its complement, which is $\{-1,1\}$, is open. But every non-empty open set is a union of sets of the form $U_{a,b}$, each of which is clearly infinite, so there can be no finite non-empty open sets. This is a contradiction and concludes the proof.

Cover Image: Passio Musicae by Eila Hiltunen, a monument to Jean Sibelius in Helsinki, Finland. Photograph by the author.