Furstenberg's Proof of the Infinitude of Primes

Theorem

There is an infinite number of primes.

Proof

Define a topology on the integers $\Z$ by declaring a subset $U \subseteq Z$ to be an open set iff it is either:

• the empty set $\varnothing$ or
• a union of sequences $S(a, b)$, where:

$S(a, b) = \{ a n + b : n \in \Z \} = a \Z + b$.

In other words, $U$ is open iff every $x \in U$ admits some non-zero integer $a$ such that $S(a,x) \subseteq U$.

The axioms for a topology are easily verified:

• By definition, $\varnothing$ is open: $\Z$ is just the sequence $S(1, 0)$, and so is open as well.

• Any union of open sets is open:

For any collection of open sets $U_i$ and $x$ in their union $U$, any of the numbers $a_i$ for which $S(a_i,x)\subseteq U_i$ also shows that $S (a_i,x) \subseteq U$.

• The intersection of two (and hence finitely many) open sets is open:

Let $U_1$ and $U_2$ be open sets and let $x \in U_1 \cap U_2$ (with numbers $a_1$ and $a_2$ establishing membership).

Set $a$ to be the lowest common multiple of $a_1$ and $a_2$.

Then $S(a,x) \subseteq S(a_i,x)\subseteq U_1 \cap U_2$.

The topology is quite different from the usual Euclidean one, and has two notable properties:

1. Since any non-empty open set contains an infinite sequence, no finite set can be open; put another way, the complement of a finite set cannot be a closed set.
2. The basis sets $S(a,b)$ are both open and closed: they are open by definition, and we can write $S(a,b)$ as the complement of an open set as follows:

$\displaystyle S(a, b) = \Z \setminus \bigcup_{j = 1}^{a - 1} S(a, b + j)$.

The only integers that are not integer multiples of prime numbers are $-1$ and $+1$, i.e.

$\displaystyle \Z \setminus \{ -1, + 1 \} = \bigcup_{p \ \text{prime}} S(p, 0)$.

By the first property, the set on the left-hand side cannot be closed. On the other hand, by the second property, the sets $S(p,0)$ are closed.

So, if there were only finitely many prime numbers, then the set on the right-hand side would be a finite union of closed sets, and hence closed.

Therefore by proof by contradiction, there must be infinitely many prime numbers.

See Also

• Euclid's Theorem and its Corollary

Source of Name

This entry was named for Hillel Furstenberg.