Prime number theorem

Before Hadamard and de la Vallée Poussin's 1896 analytic proof, Chebyshev (1852) already showed elementarily, using nothing but binomial coefficients, that the count of primes is trapped within a constant factor of x/log x. This bound is the key elementary ingredient later inputs to any proof of the full theorem, and its central-binomial-coefficient trick is the same one behind Erdős's famous elementary proof of Bertrand's postulate.

We use strong induction on $n$. Base cases $n=1,2$ are immediate: $\theta(1)=0$ and $\theta(2)=\log 2 < \log 4$.

For the inductive step, suppose the bound holds for every positive integer smaller than $n$. If $n>2$ is even, $n$ is not prime, so $\theta(n)=\theta(n-1) < (\log4)(n-1) < (\log4)n$ by the induction hypothesis applied to $n-1$.

If $n=2m+1$ is odd, consider the central binomial-type coefficient $\binom{2m+1}{m}=\dfrac{(2m+1)!}{m!\,(m+1)!}$. It appears twice among the $2^{2m+1}$ terms of the binomial expansion of $(1+1)^{2m+1}$ (once as $\binom{2m+1}{m}$, once as $\binom{2m+1}{m+1}$, and these are equal), so $2\binom{2m+1}{m} \le 2^{2m+1}$, giving $\binom{2m+1}{m} \le 4^m$.

Every prime $p$ with $m+1 < p \le 2m+1$ divides the numerator $(2m+1)!$ but divides neither $m!$ nor $(m+1)!$ (since $p>m+1$), so $p$ divides $\binom{2m+1}{m}$. Hence the product of all such primes divides $\binom{2m+1}{m}$, so $\prod_{m+1<p\le 2m+1} p \le \binom{2m+1}{m} \le 4^m$, i.e. $\theta(2m+1)-\theta(m+1) \le (\log 4)\,m$.

By the induction hypothesis applied to $m+1<n$, $\theta(m+1) < (\log4)(m+1)$. Adding, $\theta(n)=\theta(2m+1) < (\log4)(m+1) + (\log4)m = (\log4)(2m+1) = (\log4)n$, completing the induction.

Chebyshev's bound above pins π(x) to within a constant factor of x/log x, but "asymptotic to" is a much stronger claim: the ratio π(x)/(x/log x) must tend to exactly 1, not just stay bounded. Closing that gap from "bounded" to "exactly 1" needed an entirely different idea — Riemann's 1859 insight that the distribution of primes is encoded in the complex zeros of the zeta function ζ(s).

This proof is a logical sketch of the analytic route, not a self-contained derivation — it needs complex analysis introduced later in the curriculum (see the topic on the Riemann zeta function for the details). The argument has three stages.

Stage 1 (reduce to θ): a routine partial-summation argument shows $\pi(x) \sim x/\log x$ is equivalent to $\theta(x) \sim x$, where $\theta(x)=\sum_{p\le x}\log p$ as in Chebyshev's bound above.

Stage 2 (encode θ via ζ): Riemann's explicit formula expresses $\theta(x)$ (more precisely the closely related $\psi(x)=\sum_{p^k\le x}\log p$) almost exactly in terms of the zeros of $\zeta(s)=\sum_n n^{-s}=\prod_p(1-p^{-s})^{-1}$: the leading term $x$ comes from $\zeta$'s simple pole at $s=1$, and every zero $\rho=\beta+i\gamma$ of $\zeta$ contributes an oscillating error term of size roughly $x^{\beta}$.

Stage 3 (the key nonvanishing fact): $\psi(x)\sim x$ — and hence the theorem — holds if and only if no zero has $\beta=1$, i.e. $\zeta(1+it) \ne 0 \text{ for all } t \in \mathbb{R}$. Hadamard and de la Vallée Poussin proved this nonvanishing independently in 1896, using an elementary trigonometric inequality ($3+4\cos\theta+\cos2\theta\ge0$) applied to $\log|\zeta(\sigma)^3\zeta(\sigma+it)^4\zeta(\sigma+2it)|$ as $\sigma\to1^+$: a zero at $1+it$ would force this expression to $-\infty$, which the inequality forbids. Newman's 1980 proof streamlines Stage 3's consequences into a short Tauberian argument, but the logical backbone — pole at $1$, zeros elsewhere, nonvanishing on the line $\operatorname{Re}(s)=1$ — is exactly as Riemann and Hadamard laid it out.