The Riemann zeta function and the Riemann hypothesis

This uniqueness is exactly what makes the Euler product below work: expanding it out and collecting terms reproduces each $n^{-s}$ only once, with no double-counting and nothing missing.

Existence is proved by strong induction on $n$. The base case $n=2$ is already prime, so the claim holds. Suppose every integer $2\le m<n$ factors into primes, and consider $n$. If $n$ is itself prime we are done; otherwise $n=ab$ with $1<a,b<n$, and the induction hypothesis supplies prime factorizations of both $a$ and $b$. Concatenating these two factorizations produces a prime factorization of $n$, which completes the induction.

Uniqueness rests on Euclid's lemma: if a prime $p$ divides $p\mid ab$, then $(p\mid a)\lor(p\mid b)$. To see this, suppose $p\nmid a$; then $\gcd(p,a)=1$, so by Bézout's identity there are integers $x,y$ with $px+ay=1$. Multiplying by $b$ gives $b=pbx+aby$. Since $p\mid ab$, the prime $p$ divides both terms on the right, hence $p\mid b$.

Now suppose $n$ has two factorizations into primes, $n=p_1p_2\cdots p_r=q_1q_2\cdots q_s$, each list written in nondecreasing order. Since $p_1\mid q_1q_2\cdots q_s$, repeated application of Euclid's lemma shows $p_1$ divides some $q_j$, and because $q_j$ is prime this forces $p_1=q_j$. Cancelling this common factor from both products and repeating the argument on the shorter lists shows, after finitely many steps, that $r=s$ and the two factorizations agree term by term — so the prime factorization of $n$ is unique up to the order of the factors.

Euclid's classical proof (c. 300 BCE) argues by contradiction from a finite list. Later on this page, Euler gives a second, analytic proof of the same fact, using the divergence of the harmonic series at $s=1$.

Suppose, for contradiction, that there are only finitely many primes $p_1,p_2,\ldots,p_k$. Form the number $N=p_1p_2\cdots p_k+1$.

For each $i$, dividing $N$ by $p_i$ leaves remainder $1$, i.e. $N\equiv 1\pmod{p_i}$, so no $p_i$ divides $N$.

But $N>1$, so by the fundamental theorem of arithmetic proved above, $N$ has at least one prime factor $q$. Since none of $p_1,\ldots,p_k$ divides $N$, this $q$ satisfies $q\notin\{p_1,\ldots,p_k\}$ — a prime missing from our supposedly complete list, a contradiction. Hence no finite list can contain all the primes: there are infinitely many.

Expand each factor $(1-p^{-s})^{-1} = 1+p^{-s}+p^{-2s}+\cdots$ as a geometric series and multiply them all out: unique factorization means every $n^{-s}$ appears exactly once in the expanded product. The product needs infinitely many factors precisely because there are infinitely many primes — the same fact Euclid proved by elementary means, now packaged inside an analytic identity.

Fix $\operatorname{Re}(s)>1$ and expand each factor of the truncated product $P_N(s)=\prod_{p\le N}\left(1-p^{-s}\right)^{-1}$ as a geometric series, $(1-p^{-s})^{-1}=1+p^{-s}+p^{-2s}+\cdots$, since $|p^{-s}|<1$.

Multiplying these geometric series together and distributing, every term that appears is $n^{-s}$ for some integer $n$ whose prime factors are all at most $N$ — call the set of such integers $S_N$. By the fundamental theorem of arithmetic each such $n$ arises from exactly one combination of prime powers, so no term is produced twice and none is missing: $P_N(s)=\sum_{n\in S_N} n^{-s}$.

Every integer from $1$ to $N$ belongs to $S_N$, so the difference between the full series and the truncated product only involves integers not in $S_N$, all of which exceed $N$: $\zeta(s)-P_N(s)=\sum_{n\notin S_N} n^{-s}$, hence $\left|\zeta(s)-P_N(s)\right|\le\sum_{n>N} n^{-\sigma}$ where $\sigma=\operatorname{Re}(s)>1$. This tail of a convergent series tends to $0$ as $N\to\infty$, so $P_N(s)\to\zeta(s)$ and the infinite product equals the infinite sum.

Hadamard and de la Vallée Poussin proved this independently in 1896, and both proofs go through $\zeta$: the theorem is equivalent to $\zeta(s)$ having no zeros on the line $\operatorname{Re}(s)=1$. That already-proven fact is much weaker than the Riemann hypothesis (which asks for no zeros anywhere off $\operatorname{Re}(s)=\tfrac12$) — exactly why this theorem is settled while RH is not. RH would only sharpen the error term in the approximation, from roughly $x/\log x$ accuracy to the near-optimal $\sqrt{x}\log x$ shown above.

The prime number theorem is equivalent to a statement about the Chebyshev function $\psi(x)=\sum_{p^k\le x}\log p$, which weights each prime power below $x$ by the logarithm of its prime base: proving $\psi(x)\sim x$ is equivalent (by a routine partial-summation argument) to proving $\pi(x)\sim x/\log x$.

Riemann's explicit formula expresses $\psi(x)$ almost exactly in terms of the nontrivial zeros $\rho=\beta+i\gamma$ of $\zeta$, all of which satisfy $0\le\beta\le1$: $\psi(x)=x-\sum_{\rho}\frac{x^{\rho}}{\rho}-\log(2\pi)-\tfrac12\log(1-x^{-2})$. The leading term $x$ comes from the simple pole of $\zeta$ at $s=1$; every other term oscillates with size roughly $x^{\beta}$, so the theorem reduces to showing that this oscillating sum is $o(x)$.

The oscillating sum is $o(x)$ exactly when no zero has $\beta=1$, i.e. when $\zeta(1+it)\ne0$ for all $t\in\mathbb{R}$. Hadamard and de la Vallée Poussin each proved this non-vanishing in 1896 using the elementary trigonometric inequality $3+4\cos\theta+\cos2\theta\ge0$, applied to the real part of $3\log\zeta(\sigma)+4\log\zeta(\sigma+it)+\log\zeta(\sigma+2it)$ as $\sigma\to1^+$: a zero at $1+it$ would force this combination to diverge to $-\infty$, which the inequality forbids.

Combining the two steps gives $\psi(x)=x+o(x)$, and the partial-summation identity that links $\psi$ and $\pi$ then upgrades this to $\pi(x)\sim x/\log x$, which is the prime number theorem.