[Euler's Mathematics] Two Proofs That There Are Infinitely Many Primes

[欧拉数学]素数有无穷多个的两个证明 苏剑林 · 2011-10-02 · Mathematics prime number number theory euler mathematics

Primes are the basic units of numbers, much like bricks in a tall building. Clearly, the fact that there are infinitely many primes is a prerequisite for number theory to be a worthwhile subject at all. Otherwise, the study of numbers would be confined to a finite set of primes, and a great many numbers would lose their charm. It's a bit like how, with only a finite supply of bricks, you could never build architectural marvels. Below I'll present two classic proofs that there are infinitely many primes. One is Euclid's proof, the most original and simplest of all — I imagine many readers have already learned it, but I'll mention it here anyway. The other is one I came across in How to Solve It, originally due to Euler, and it too is a wonderfully elegant proof. Of course, this post emphasizes the underlying idea, and the reasoning may be a bit loose in places here and there — readers are welcome to tighten it up. ^_^

I. Euclid's Proof

The idea behind this proof is extremely simple: multiplying together a bunch of primes and adding 1 will produce a new prime factor. Suppose there were only n primes. Then we multiply them all together and add 1 — what do we get? If the result is itself prime, that contradicts the assumption that there are only n primes. If it's composite, then since dividing it by any of the original n primes never gives an integer, it must have some new prime factor — again contradicting the assumption that there are only n primes. Either way, assuming there are only finitely many primes leads to a contradiction, so there must be infinitely many primes. more

II. Euler's Classic Proof

This proof requires a bit of setup. The idea is: geometric series + generating function.

First, we have the formula $S(p)=1+p^{-1}+p^{-2}+...+p^{-n}=\frac{1-p^{-n-1}}{1-p^{-1}}$, the summation formula for a geometric series. When $|p| > 1,n\to \infty$, $p^{-n-1} \to 0$, we have:

$$S(p)=\sum_{n=0}^{\infty} p^{-n}=\frac{1}{1-p^{-1}}=\frac{p}{p-1}$$

Now let's try letting p range over all the primes, i.e., 2, 3, 5, 7, ..., and multiply together the corresponding S(p), obtaining (call it K):

$$\begin{aligned}K=S(2)\cdot S(3)\cdot S(5)... \\ =(1+\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}...)(1+\frac{1}{3}+\frac{1}{3^2}+\frac{1}{3^3}...)(1+\frac{1}{5}+\frac{1}{5^2}+\frac{1}{5^3}...)... \\ =\frac{2}{2-1}\cdot \frac{3}{3-1}\cdot \frac{5}{5-1}\cdot ...\end{aligned}$$

What's special about K? Notice that here, powers of each prime get multiplied together exactly once across all the terms, which is exactly how natural numbers are generated: multiplying together powers of various primes gives you any natural number you like. So we can (not without justification) write:

$$K=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...$$

Now, we know that the series $1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...$ diverges, so there cannot be only finitely many primes, because $K=\frac{2}{2-1}*\frac{3}{3-1}*\frac{5}{5-1}*...$ — if there were only finitely many primes, this product would necessarily be finite too, which would be a contradiction. Hence there are infinitely many primes.

III. A Loose Connection to the Prime Number Theorem

The prime number theorem tells us that the number of primes not exceeding n, $\pi(n)$, is approximately $\frac{n}{ln n}$.

From the discussion above, we obtained:

$$K=\frac{2}{2-1}\cdot \frac{3}{3-1}\cdot \frac{5}{5-1}\cdot ...=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...$$

Calculus can be used to show that the right-hand side of the second equality, namely $1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...+\frac{1}{n}$, can be approximated as $ ln n$. Flipping the equation around, we then get:

$$\frac{2-1}{2}\cdot \frac{3-1}{3}\cdot \frac{5-1}{5}\cdot ...\approx \frac{1}{ln n}$$

Now, for large n, the number of even numbers not exceeding n is clearly approximately $n/2$. Among the remaining $n/2$ odd numbers, the multiples of 3 number approximately $1/3$, so the non-multiples of 3 number approximately $n*1/2*2/3$. Among what's left, the non-multiples of 5 clearly number approximately $n*1/2*2/3*4/5$, and so on, giving us:

$$\pi(n) \approx n\cdot 1/2\cdot 2/3\cdot 4/5\cdot 6/7\cdot ... \approx \frac{n}{ln n}$$

Of course, this is nowhere near a rigorous proof — at best it's a piece of reasoning that happens to succeed, somewhat by luck. Still, even though it can't withstand strict logical scrutiny, it's quite fun to appreciate as a piece of elementary reasoning. ^_^