This will be the final installment on primes for my introduction to number theory series. Again, these discussions are motivated by the book
Proofs from THE BOOK by Aigner and Ziegler in honors of the late Paul Erdos.
So far we have seen two proofs for the infinitude of primes that use pure number theory and one that uses abstract algebra. We will now top it all off with a proof that uses elementary calculus. To easily understand the proof, we need to know the basics about the following topics:
- Riemannian Integral Approximations (i.e. Estimating the area under a graph using rectangles.)
- Geometric Series: $latex \sum_{n=1}^\infty x^n, \text{for} \left| x \right| < 1$
- The integral of the log function.
Seems surprisingly simple, yes? Let's see exactly how simple in the last proof which I will present here.
Theorem. There are infinitely many prime numbers
Proof. Let's begin by defining the "prime counting" function,
$latex \pi(x) = \#\{ p \leq x : p \in \mathbb{P} \}$
where $latex \mathbb{P} = { p_1, p_2, \ldots }$ is the set of all prime numbers in increasing order. That is, $latex \pi(x)$ is the number of primes less than $latex x$. (Note that we do not assume that there are infinitely many elements of this set. This is exactly what we're trying to prove.) Now, consider the natural logarithm function defined as the area underneath the function $latex f(t) = \frac{1}{t}$.
$latex \log(x) = \int_1^x \frac{1}{t}dt$
Recall from high school calculus that one can use
upper and lower step functions to approximate the value of an integral, otherwise called the "rectangle method". One approximation of $latex \log(x)$ would be to draw a rectangle at each integer $latex n < x$, as shown in the picture below.
[[[INSERT AN UPPER STEP FUNCTION PIC]]]
Since the upper step function is always greater than or equal to the actual value of the integral, we have the following inequality for $latex n \leq x < n+1$
$latex \log(x) \leq 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}$
$latex .\qquad \qquad \qquad \qquad \quad \leq \sum \frac{1}{m}$
where the sum is over all $latex m \in \mathbb{N}$ such that each prime divisor $latex p$ of $latex m$ is less than $latex x$. Now, since every such $latex m$ can be
uniquely written as a product of primes $latex \prod_{p \leq x} p^{k_p}$, this last sum can be written
$latex \prod_{p \in \mathbb{P}, p \leq x} \left( \sum_{k \geq 0} \frac{1}{p^k} \right).$
The inner sum is a geometric series, meaning that $latex \sum \frac{1}{p^k} = \frac{1}{1-\frac{1}{p}}$, and therefore
$latex \log(x) \leq \prod_{p \in \mathbb{P}, p \leq x} \frac{1}{1 - \frac{1}{p}} = \prod_{p \in \mathbb{P}, p \leq x} \frac{p}{p-1} = \prod_{k=1}^{\pi(x)} \frac{p_k}{p_k - 1}.$
Since the $latex k^\text{th}$ prime, $latex p_k$, is greater than or equal to $latex k + 1$ (check for yourself), we have
$latex \frac{p_k}{p_k - 1} = 1 + \frac{1}{p_k - 1} \leq 1 + \frac{1}{k} = \frac{k}{k+1},$
and therefore
$latex \log(x) \leq \prod_{k=1}^{\pi(x)} \frac{k+1}{k} = \pi(x) + 1.$
Since $latex \log(x)$ is unbounded, we conclude that $latex \pi(x)$ is also unbounded as well, thus completing the proof.
$latex \square$
I hope you enjoyed these four beautiful proofs! Be on the lookout for more proofs from THE BOOK. Again, my main reference is "Proofs from THE BOOK (Third Edition)" by Martin Aigner and Gunter M. Ziegler. And if you have a BOOK proof of your own, please post a link below!
