prime numbers | Matt Baker's Math Blog

A few years ago I discovered an amusing proof of Euclid’s theorem that there are infinitely many primes which I thought I’d record here for posterity. (I subsequently learned that a similar argument appears in this paper by Paul Pollack.)

To motivate the proof, and illustrate its working in an (admittedly silly) special case, suppose that there were just two prime numbers, called p and q. Then by the fundamental theorem of arithmetic (i.e., unique factorization into primes) we would have the following identity between generating functions:

$\sum_{n=2}^\infty z^n = \sum_{k=1}^\infty z^{kp} + \sum_{k=1}^\infty z^{kq} - \sum_{k=1}^\infty z^{kpq}.$

Indeed, there is precisely one term $z^n$ for each integer $n \geq 2$ on the left-hand side, and the same is true for the right-hand side (consider separately the cases where $p \mid n$ but $q \nmid n$ , $q \mid n$ but $p \nmid n$ , and $pq \mid n$ ). Using the formula for the sum of a geometric series, we can rewrite our formula as an identity between complex-analytic functions valid on the open unit disc ${\mathbb D} = \{z \in {\mathbb C} \; : \; |z|<1 \}$ :

$\frac{z^2}{1-z} = \frac{z^p}{1-z^p} + \frac{z^q}{1-z^q} - \frac{z^{pq}}{1-z^{pq}}.$

This is impossible, however, as we see by letting $z$ approach a primitive $pq^{\rm th}$ root of unity, since each term stays bounded except for $\frac{z^{pq}}{1-z^{pq}}$ , which tends to infinity.