Furstenberg’s proof of the infinitude of the primes

Another very classical proof that’s just too beautiful to ignore. This time, the theorem is millennia old, but it’s really the proof that I’m interested in.

Lemma. There are infinitely many primes.

Proof. Define the sets

    \[ U_{a,n} = a + n\Z = \{x \in \Z\ |\ x \equiv a \pmod{n}\}, \]

for a, n \in \Z with n \neq 0. Note that if U_{a,n} \cap U_{b,m} \neq \varnothing; say it contains some c \in \Z, then

    \[ U_{a,n} \cap U_{b,m} = U_{c, \lcm (n,m)}. \]

Hence, the intersection of two sets of this form is again of this form (or empty). Thus, they form the basis for a topology \scr{T} on \Z. Notice that the sets

    \[ U_{a,n}\comp = \bigcup_{b \not \equiv a} U_{b,n} \]

are also open.

Now suppose that there were finitely many primes. Then the intersection

    \[ V = \bigcap_{p \text{ prime}} U_{0,p}\comp \]

is a finite intersection of opens, hence open. On the other hand, it equals the set of integers divisible by no prime number, which is \{1, -1\}. But all basic open sets are infinite, so this set can never be open. \qedsymbol

Remark. This proof is in essence the usual proof, where we consider p_1 \cdots p_n + 1 and conclude that some prime has to divide it and this prime can be none of the p_i. Indeed, when we showed that the intersection of basic opens is open, we went to a set whose period is \lcm(n,m) (which for V gives period p_1 \cdots p_n). Since 1 is in V, so should p_1 \cdots p_n + 1 be.

That said, it doesn’t seem possible to adopt this proof to reprove other theorems like ‘there are infinitely many primes congruent to 3 modulo 4’. The problem is that the above proof seems to rely on a global analysis of the set V: it has to be an infinite set. So the method is too crude to prove theorems with congruence restrictions.

Cauchy’s theorem

This is a really classical result, but this proof is just so magical that I have to include it.

Lemma. Let G be a finite group, and let p be a prime dividing \# G. Then G has an element of order p.

Proof. Consider the action of \Z/p\Z = \langle \sigma \rangle on

    \[ X = \{(g_1, \ldots, g_p) \in G^p\ |\ g_1 \cdots g_p = 1\} \]

given by

    \[ \sigma \cdot (g_1, \ldots, g_p) = (g_2, \ldots, g_p, g_1). \]

Then \# (X^{\Z/p\Z}) \equiv \# X \pmod{p}, since the orbits of size > 1 all have size p (and the fixed points X^{\Z/p\Z} are exactly the union of the orbits of size 1). The right hand side is 0 \pmod{p} as p \mid \# G. Thus,

    \[ \# (X^{\Z/p\Z}) \equiv 0 \pmod{p}. \]

But there is a bijection

    \begin{align*} \{g \in G\ |\ g^p = 1\} &\rA X^{\Z/p\Z}\\ g &\rM (g, \ldots, g). \end{align*}

The former trivially contains the element 1, hence (since its size is divisible by p) it has to contain some other element g. This element will then have (exact) order p. \qedsymbol

Remark. Of course, the result also follows from the much stronger Sylow theorems (of which we only need the existence statement).