Euler's Proof: There are Infinitely Many Primes
Theorem
There are infinitely many primes.
Proof
Strategy: It does not matter what method one uses as long as it reaches the same result, but if it is solved in a truly unusual way, then it is worth studying in its own right. It lacks the simple, clear, and clean flavor of Euclid’s proof, but the fact that it solves a problem in number theory with analytic tools is very interesting. As with many of the proofs Euler left behind, it delivers a shock that is hard to forget once you have seen it. Let us follow the genius’s line of thought and savor the proof itself.
Consider the harmonic series $$ \sum_{ n = 1 }^{ \infty } {{1} \over {n}} = 1 + {{1} \over {2}} + {{1} \over {3}} + {{1} \over {4}} + {{1} \over {5}} + {{1} \over {6}} + \cdots $$ If we group the terms where $n$ is a power of a prime, then $$ \sum_{ n = 1 }^{ \infty } {{1} \over {n}} = 1 + \left( {{1} \over {2}} + {{1} \over {4}} + \cdots \right) + \left( {{1} \over {3}} + {{1} \over {9}} + \cdots \right) + \left( {{1} \over {5}} + {{1} \over {25}} + \cdots \right) + \cdots+ {{1} \over {6}} + \cdots $$ Meanwhile, by the Fundamental Theorem of Arithmetic, there is a one-to-one correspondence between a natural number and its prime factorization. For example, since $6= 2 \cdot 3$, picking $\displaystyle {{1} \over {2}}$ and $\displaystyle {{1} \over {3}}$ respectively from $\displaystyle \left( {{1} \over {2}} + {{1} \over {4}} + \cdots \right)$ and $\displaystyle \left( {{1} \over {3}} + {{1} \over {9}} + \cdots \right)$ and multiplying them yields exactly one $\displaystyle {{1} \over {6}}$. Since any natural number is produced exactly once by picking and multiplying terms from among the powers of primes, the harmonic series can be written as $$ \sum_{ n = 1 }^{ \infty } {{1} \over {n}} = \left( 1 + {{1} \over {2}} + {{1} \over {4}} + \cdots \right) \left( 1 + {{1} \over {3}} + {{1} \over {9}} + \cdots \right) \left( 1 + {{1} \over {5}} + {{1} \over {25}} + \cdots \right) \cdots $$ Rearranging with geometric series, we get $$ \sum_{ n = 1 }^{ \infty } {{1} \over {n}} = \left( {{1} \over {1 - {{1} \over {2}} }} \right) \left( {{1} \over {1 - {{1} \over {3}} }} \right) \left( {{1} \over {1 - {{1} \over {5}} }} \right) \cdots $$ Expressing this concisely as a product, for a prime $p$, $$ \sum_{ n = 1 }^{ \infty } {{1} \over {n}} = \prod_{p} \left( 1 - {{1} \over {p}} \right)^{-1} $$ Meanwhile, for every prime $p$, $$ \left( 1 - {{1} \over {p}} \right)^{-1} = {{1} \over {1 - {{1} \over {p}} }} > 1 $$ so the fact that $\displaystyle \prod_{p} \left( 1 - {{1} \over {p}} \right)^{-1}$ diverges means that there are infinitely many primes $p$. Of course, since the harmonic series diverges, $$ \prod_{p} \left( 1 - {{1} \over {p}} \right)^{-1} = \sum_{ n = 1 }^{ \infty } {{1} \over {n}} = \infty $$ and therefore there are infinitely many primes.
■