Primes and the Prime Number Theorem: From Infinitude and Unique Factorization to the Law of Distribution

0. Key points

• Primes are the atoms of multiplication. Every integer factors into primes, and the factorization is unique up to order (the fundamental theorem of arithmetic). This uniqueness is not self-evident: proving it requires a detour through Bézout’s identity.
• There are infinitely many primes. Euclid’s proof is 2300 years old, but Euler strengthened it to the far more quantitative statement $\sum_p 1/p = \infty$.
• The number $\pi(x)$ of primes up to $x$ is asymptotic to $x/\log x$ (the prime number theorem). The intuition “an integer near $n$ is prime with probability about $1/\log n$” is, verbatim, a theorem.
• The prime number theorem itself needs complex analysis, but merely staring at the binomial coefficient $\binom{2n}{n}$ yields upper and lower bounds of the correct order for $\pi(x)$ (Chebyshev-type bounds). We prove those bounds completely here.
• We know the average shape of the distribution, yet almost nothing about the behaviour of individual primes. The twin prime conjecture and the Goldbach conjecture are both open, and sharpening the error term is precisely the Riemann hypothesis.

1. Motivation

Primes, learned in primary school as “numbers divisible only by $1$ and themselves”, are among the first concepts one meets in mathematics. Even so, a substantial fraction of the basic questions about them remain unanswered today. That gap is where number theory begins.

Historically, the first theorem about primes is Proposition 20 of Book IX of Euclid’s Elements: “prime numbers are more than any assigned multitude of prime numbers”. The word “infinite” was avoided; the claim was stated constructively, as the assertion that given any finite list of primes one can produce a prime outside it. Read today, that formulation has not aged.

The next large step was to ask not for the number of primes but for their density. Around the age of fifteen (1792–93) Gauss, poring over tables of primes, noticed that the count of primes below $x$ is well approximated by $\int_2^x dt/\log t$. At about the same time Legendre proposed the approximation $x/(\log x - 1.08366)$. Both were conjectures, not proofs. Around 1850 Chebyshev established, by elementary arguments alone, that $\pi(x)$ lies between constant multiples of $x/\log x$ — that is, he pinned down the correct order of magnitude. In his 1859 memoir Riemann gave a framework expressing $\pi(x)$ in terms of the zeros of the zeta function $\zeta(s)$, and Hadamard and de la Vallée Poussin, completing that framework analytically, proved the prime number theorem independently in 1896. About a century had passed since Gauss’s observation.

This article follows that thread in the following order. First we set up the definition of a prime together with the most basic tools of number theory, the division algorithm and Bézout’s identity. Next we prove Euclid’s theorem and the fundamental theorem of arithmetic. We then prove two quantitative results measuring how numerous the primes are (Euler’s divergence theorem and Chebyshev’s bounds), state the prime number theorem, and finally survey the open problems. If the proof techniques themselves are unfamiliar, read Techniques of Proof first.

2. Preliminaries: divisibility and greatest common divisors

Throughout, unless stated otherwise, all letters denote integers. We set $\mathbb{N} = \{1, 2, \ldots\}$, excluding $0$.

Definition 2.1（Divisibility and greatest common divisor）

For integers $a, b$, we say that $a$ divides $b$, written $a \mid b$, if there is an integer $c$ with $b = ac$. When $a$ does not divide $b$ we write $a \nmid b$.

If $a$ and $b$ are not both $0$, the greatest common divisor $\gcd(a,b)$ is defined to be the largest of the common divisors of $a$ and $b$. Every common divisor is at most $\min(|a|,|b|)$, so the maximum exists. When $\gcd(a,b) = 1$ we call $a$ and $b$ coprime.

Definition 2.2（Primes and composites）

An integer $p > 1$ is prime if its only positive divisors are $1$ and $p$. An integer greater than $1$ that is not prime is called composite. The number $1$ is neither prime nor composite.

Excluding $1$ from the primes is not a convention of convenience but a necessity. If $1$ were prime we would have $6 = 2\cdot 3 = 1 \cdot 2\cdot 3 = 1\cdot 1\cdot 2\cdot 3$, and the uniqueness of prime factorization proved below would collapse.

Lemma 2.3（Division algorithm）

Let $a$ be an integer and $b$ a positive integer. Then there is exactly one pair $(q, r)$ of integers with

$$a = bq + r, \qquad 0 \le r < b.$$

Proof（Lemma 2.3）

Existence. Consider the set $S = \{a - bq : q \in \mathbb{Z},\ a - bq \ge 0\}$. Taking $q = -|a|$ gives $a - bq = a + b|a| \ge a + |a| \ge 0$ (we used $b \ge 1$), so $S \ne \varnothing$. Being a nonempty set of nonnegative integers, $S$ has a least element $r = a - bq$ by well-ordering（Axiom 3.1）［Techniques of Proof］. If $r \ge b$, then $r - b = a - b(q+1) \ge 0$ would also lie in $S$ with $r - b < r$, contradicting minimality of $r$. Hence $0 \le r < b$.

Uniqueness. Suppose $bq + r = bq' + r'$ with $0 \le r, r' < b$. Then $b(q - q') = r' - r$. From $0 \le r, r' < b$ we get $|r' - r| < b$, so $b|q - q'| < b$, that is $|q - q'| < 1$; hence $q = q'$ and therefore $r = r'$.

∎

Lemma 2.4（Bézout's identity）

Let $a, b$ be integers, not both $0$, and put $d = \gcd(a, b)$. Then there exist integers $x_0, y_0$ with $d = ax_0 + by_0$. Moreover $d$ is the least positive integer belonging to the set $I = \{ax + by : x, y \in \mathbb{Z}\}$.

Proof（Lemma 2.4）

Since $a^2 + b^2 > 0$ lies in $I$, the set of positive integers in $I$ is nonempty, and by well-ordering it has a least element $d_0 = ax_0 + by_0$.

We first show $d_0 \mid a$. By Lemma 2.3 we may write $a = d_0 q + r$ with $0 \le r < d_0$. Then

$$r = a - d_0 q = a - (ax_0 + by_0)q = a(1 - qx_0) + b(-qy_0) \in I$$

If $0 < r < d_0$ this would contradict the minimality of $d_0$, so $r = 0$, that is $d_0 \mid a$. The same argument gives $d_0 \mid b$, so $d_0$ is a common divisor of $a$ and $b$.

Next, let $c$ be any common divisor of $a$ and $b$. Then $c \mid ax_0 + by_0 = d_0$, so $c \le |c| \le d_0$. Hence $d_0$ is the largest common divisor, and by the definition in Definition 2.1 we get $d_0 = \gcd(a,b) = d$.

∎

Note

Bézout’s identity is an elementary restatement of the assertion that every ideal of $\mathbb{Z}$ is principal. We return to this viewpoint in Rings and Fields. Rewritten in the language of ideals, the statement is Proposition 7.2［イデアルと剰余環］.

3. The infinitude of primes

Lemma 3.1（The least divisor is prime）

Every integer $n > 1$ has at least one prime factor. More precisely, the least of the positive divisors of $n$ exceeding $1$ is prime.

Proof（Lemma 3.1）

The set of positive divisors of $n > 1$ exceeding $1$ contains $n$ itself, so it is nonempty; by well-ordering it has a least element $p$. If $p$ were not prime, there would be a divisor $e$ of $p$ with $1 < e < p$. From $e \mid p$ and $p \mid n$ we get $e \mid n$, so $e$ is a divisor of $n$ exceeding $1$ with $e < p$, contradicting the minimality of $p$. Hence $p$ is prime.

∎

Theorem 3.2（Euclid's theorem）

There are infinitely many primes. That is, for any finitely many primes $p_1, \ldots, p_k$ there exists a prime different from all of them.

Proof（Theorem 3.2）

Let $p_1, \ldots, p_k$ be any finite collection of primes and set

$$N = p_1 p_2 \cdots p_k + 1$$

Since each $p_i \ge 2$ we have $N \ge 3 > 1$. By Lemma 3.1, $N$ has a prime factor $q$.

If $q = p_i$ for some $i$, then $q \mid p_1\cdots p_k$ and $q \mid N$, whence $q$ divides the difference, $q \mid N - p_1\cdots p_k = 1$. But primes are at least $2$, so $q \mid 1$ is impossible. Hence $q$ is a prime distinct from every $p_1, \ldots, p_k$.

Assuming there were only finitely many primes $p_1, \ldots, p_k$, the prime $q$ just constructed would fail to be on the list — a contradiction. Therefore there are infinitely many primes.

∎

Example 3.3（$p_1\cdots p_k + 1$ need not be prime）

This proof is often misreported as saying that adding $1$ to the product of the first $k$ primes produces a new prime. What it actually produces is a number possessing a new prime factor; there is no guarantee that the number itself is prime. The first few cases are indeed prime:

$$2+1 = 3,\quad 2\cdot3+1 = 7,\quad 2\cdot3\cdot5+1 = 31,\quad 2\cdot3\cdot5\cdot7+1 = 211,\quad 2\cdot3\cdot5\cdot7\cdot11+1 = 2311$$

are all prime. At the next stage this breaks down:

$$2\cdot3\cdot5\cdot7\cdot11\cdot13 + 1 = 30030 + 1 = 30031 = 59 \times 509.$$

Indeed $59 \times 509 = 59\times 500 + 59\times 9 = 29500 + 531 = 30031$. So $30031$ is composite, yet neither of its prime factors $59$ and $509$ belongs to $\{2,3,5,7,11,13\}$. That, and nothing more, is what the proof claims.

4. The fundamental theorem of arithmetic

We now know there are infinitely many primes. Next we examine how the primes assemble the integers.

Lemma 4.1（Euclid's lemma）

Let $p$ be prime and $a, b$ integers. If $p \mid ab$, then $p \mid a$ or $p \mid b$.

Proof（Lemma 4.1）

If $p \mid a$ the conclusion holds, so assume $p \nmid a$ and let us show $p \mid b$.

Since $\gcd(p, a)$ is a positive divisor of $p$, by Definition 2.2 it equals $1$ or $p$. If $\gcd(p,a) = p$ then $p \mid a$, contrary to assumption, so $\gcd(p, a) = 1$. By Lemma 2.4 there are integers $x, y$ with

$$1 = px + ay$$

Multiplying both sides by $b$ gives

$$b = pbx + (ab)y$$

The first term on the right is a multiple of $p$, and so is the second by the hypothesis $p \mid ab$. Hence $p \mid b$.

∎

The statement of the lemma is special to primes: it fails for composite $p$. Taking $p = 6$, $a = 2$, $b = 3$ we have $6 \mid 6 = ab$ but $6 \nmid 2$ and $6 \nmid 3$.

Theorem 4.2（Fundamental theorem of arithmetic）

Every integer $n > 1$ can be written as a product of primes, and the representation is unique up to the order of the factors. That is, if

$$n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s$$

with $p_i, q_j$ prime, $p_1 \le \cdots \le p_r$ and $q_1 \le \cdots \le q_s$, then $r = s$ and $p_i = q_i$ for every $i$.

Proof（Theorem 4.2）

Existence. We argue by strong induction on $n$ (complete induction（Theorem 4.3）［Techniques of Proof］). For $n = 2$, which is prime, we have a product of one factor. Let $n > 2$ and assume the claim for all integers from $2$ to $n-1$. If $n$ is prime it is its own representation. If $n$ is composite we may write $n = ab$ with $1 < a < n$ and $1 < b < n$. By the inductive hypothesis $a$ and $b$ are each products of primes, and concatenating these gives a representation of $n$ as a product of primes.

Uniqueness. We induct on $r$, taking as the statement indexed by $r$ that the number is expressible as a product of $r$ primes.

Case $r = 1$. Here $p_1 = q_1\cdots q_s$ with $p_1$ prime. If $s \ge 2$ then $q_1 \mid p_1$ and $1 < q_1 < q_1 q_2 \cdots q_s = p_1$, contradicting the primality of $p_1$ (Definition 2.2). Hence $s = 1$ and $p_1 = q_1$.

Let $r \ge 2$ and assume uniqueness for products of $r - 1$ primes. Since $p_1 \mid q_1 q_2\cdots q_s$, applying Lemma 4.1 repeatedly $s-1$ times yields $p_1 \mid q_j$ for some $j$. The positive divisors of $q_j$ are $1$ and $q_j$ only, and $p_1 > 1$, so $p_1 = q_j$. Running the same argument in the other direction gives $q_1 = p_i$ for some $i$. Therefore

$$p_1 \le p_i = q_1 \le q_j = p_1$$

and hence $p_1 = q_1$ (this is where we use that the factors are listed in increasing order). Dividing both sides by $p_1$ gives

$$p_2 \cdots p_r = q_2 \cdots q_s$$

an identity whose left side is a product of $r-1$ primes. By the inductive hypothesis $r - 1 = s - 1$ and $p_i = q_i$ for $i \ge 2$, which is the assertion.

∎

Collecting equal primes, every $n > 1$ can be written uniquely as

$$n = p_1^{e_1} p_2^{e_2}\cdots p_k^{e_k}$$

with distinct primes $p_1 < \cdots < p_k$ and positive integers $e_1, \ldots, e_k$. For a prime $p$ we write $v_p(n)$ for the largest $e$ with $p^{e} \mid n$, and call it the $p$-adic valuation.

Example 4.3（Irrationality of $\sqrt{2}$）

Here is a typical use of unique factorization. If $\sqrt 2$ were rational we could write $\sqrt 2 = a/b$ with $a, b \in \mathbb{N}$, so that $a^2 = 2b^2$. Apply $v_2$ to both sides. Since $v_2(a^2) = 2v_2(a)$ and $v_2(2b^2) = 1 + 2v_2(b)$, we get

$$2v_2(a) = 1 + 2v_2(b)$$

whose left side is even and right side odd — a contradiction. What licenses the claim that the two sides have the same $v_2$ is precisely the uniqueness of factorization, Theorem 4.2. Without uniqueness the argument does not get off the ground. The classical proof using fractions in lowest terms is in Theorem 7.5［Techniques of Proof］.

Remark 4.4（Unique factorization is not automatic）

Uniqueness looks obvious only because we are used to $\mathbb{Z}$. In the ring $\mathbb{Z}[\sqrt{-5}] = \{a + b\sqrt{-5} : a, b \in \mathbb{Z}\}$ we have

$$6 = 2\cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$$

and none of $2, 3, 1\pm\sqrt{-5}$ factors further in this ring (consider the norm $N(a+b\sqrt{-5}) = a^2 + 5b^2$: we have $N(2) = 4$, $N(3) = 9$, $N(1\pm\sqrt{-5}) = 6$, and no element has $N(x) = 2$ or $N(x) = 3$). So the factorization is genuinely two-fold (this example is treated in more detail in Example 3.1［フェルマーの最終定理］). What makes uniqueness work in $\mathbb{Z}$ is Lemma 2.4, hence the division algorithm — by no means a general phenomenon. Repairing this failure is the starting point of ideal theory, and it connects directly to the history of Fermat’s Last Theorem.

flowchart TD
A["Division algorithm"] --> B["Bézout's identity"]
B --> C["Euclid's lemma"]
C --> D["Fundamental theorem of arithmetic (unique factorization)"]
D --> E["Euler product"]
E --> F["Divergence of Σ 1/p"]
D --> G["Prime factorization of binomial coefficients"]
G --> H["Chebyshev-type bounds"]
E --> I["Prime number theorem"]
H --> I
I --> J["Riemann hypothesis and the error term"]

The logical skeleton of this article: from the division algorithm through unique factorization to the distribution of primes

5. How numerous are the primes?

Definition 5.1（The prime counting function and asymptotic equivalence）

For a real number $x$, write $\pi(x)$ for the number of primes not exceeding $x$; that is, $\pi(x) = \#\{p : p \text{ prime},\ p \le x\}$. For instance $\pi(10) = 4$ (namely $2,3,5,7$) and $\pi(100) = 25$.

For positive functions $f, g$ we write $f(x) \sim g(x)$ (as $x \to \infty$) when $\lim_{x\to\infty} f(x)/g(x) = 1$, and say that $f$ and $g$ are asymptotically equivalent.

Theorem 5.2（Euler: divergence of the sum of reciprocals of primes）

For every real number $x \ge 2$,

$$\sum_{p \le x} \frac{1}{p} \ge \log\log x - \frac{1}{2}$$

where the sum runs over all primes $p \le x$. In particular $\sum_{p} 1/p = \infty$, and there are infinitely many primes.

Proof（Theorem 5.2）

Step 1: a lower bound for the harmonic sum. For $n \le t \le n+1$ we have $1/n \ge 1/t$, so $\frac1n \ge \int_n^{n+1}\frac{dt}{t}$. Summing over $n = 1, \ldots, \lfloor x\rfloor$ gives

$$\sum_{n \le x}\frac1n \ \ge\ \int_1^{\lfloor x\rfloor + 1}\frac{dt}{t} \ \ge\ \int_1^{x}\frac{dt}{t} = \log x$$

(we used $\lfloor x\rfloor + 1 > x$).

Step 2: the Euler product inequality from unique factorization. Fix $x \ge 2$. For each prime $p \le x$ we have $0 < 1/p \le 1/2 < 1$, so the geometric series

$$\left(1 - \frac1p\right)^{-1} = \sum_{k=0}^{\infty} \frac{1}{p^{k}}$$

converges. There are only finitely many primes below $x$, so we may multiply these series together and expand term by term. Each term of the expansion has the form $1/(p_1^{k_1}\cdots p_m^{k_m})$ with $p_1, \ldots, p_m$ distinct primes $\le x$. By Theorem 4.2 such tuples of exponents correspond bijectively to the positive integers $n$ all of whose prime factors are $\le x$. Hence

$$\prod_{p \le x}\left(1 - \frac1p\right)^{-1} = \sum_{n \in A(x)} \frac1n, \qquad A(x) = \{n \in \mathbb{N} : \text{every prime factor of } n \text{ is} \le x\}$$

If $n \le x$ then every prime factor of $n$ is at most $n$, hence at most $x$, so $\{n \in \mathbb{N} : n \le x\} \subset A(x)$; all terms are positive, so combining with Step 1,

$$\prod_{p \le x}\left(1 - \frac1p\right)^{-1} \ \ge\ \sum_{n\le x}\frac1n \ \ge\ \log x$$

Step 3: take logarithms and convert to a sum. Taking logarithms of both sides,

$$\sum_{p \le x} \left(-\log\left(1 - \frac1p\right)\right) \ \ge\ \log\log x$$

Now for $0 < t < 1$ we have $-\log(1-t) = \sum_{k\ge1} t^k/k$, whence

$$-\log(1-t) \le t + \frac12\sum_{k \ge 2} t^{k} = t + \frac{t^2}{2(1-t)}$$

(using $1/k \le 1/2$ for $k \ge 2$). Setting $t = 1/p$,

$$-\log\left(1 - \frac1p\right) \le \frac1p + \frac{1}{2p^2}\cdot\frac{p}{p-1} = \frac1p + \frac{1}{2p(p-1)}$$

Bounding the sum over primes by the sum over all integers,

$$\sum_{p} \frac{1}{2p(p-1)} \le \frac12\sum_{m \ge 2}\frac{1}{m(m-1)} = \frac12\sum_{m\ge2}\left(\frac{1}{m-1} - \frac1m\right) = \frac12$$

(a telescoping sum). Therefore

$$\log\log x \le \sum_{p\le x}\left(-\log\left(1-\frac1p\right)\right) \le \sum_{p \le x}\frac1p + \frac12$$

and rearranging gives the assertion. As $x \to \infty$ the right-hand side diverges to $\infty$, so $\sum_p 1/p = \infty$. If there were only finitely many primes the sum would be finite; hence there are infinitely many.

∎

This theorem carries more information than Theorem 3.2. Since the sum of reciprocals of the squares converges, $\sum 1/n^2 = \pi^2/6$ (the Basel problem（Example 3.5）［リーマン予想とは何か］), it tells us that the primes are distributed more densely than the squares. At the same time the growth $\sum_{p\le x} 1/p \approx \log\log x$ is extraordinarily slow, so it also shows that the primes are quite thin.

Proposition 5.3（Chebyshev-type bounds）

$$\liminf_{x\to\infty}\frac{\pi(x)\log x}{x} \ \ge\ \log 2 = 0.6931\ldots, \qquad \limsup_{x\to\infty}\frac{\pi(x)\log x}{x} \ \le\ \log 4 = 1.3862\ldots$$

Thus $\pi(x)$ differs from $x/\log x$ by at most a constant factor.

Proof（Proposition 5.3）

We prove the lower bound here and defer the upper bound to the Appendix.

Let $n$ be a positive integer and consider the central binomial coefficient $C = \binom{2n}{n}$.

Step 1: $C$ is large. By the binomial theorem $\sum_{k=0}^{2n}\binom{2n}{k} = 2^{2n} = 4^n$. The left side is a sum of $2n+1$ terms, of which $\binom{2n}{n}$ is the largest ($\binom{2n}{k}$ attains its maximum at $k = n$). Hence

$$(2n+1)\,C \ \ge\ 4^n, \qquad \text{that is}\qquad C \ \ge\ \frac{4^n}{2n+1}.$$

Step 2: the prime factors of $C$ are small, and so are their exponents. We have $C = (2n)!/(n!)^2$. The exponent of a prime $p$ in $m!$ is

$$v_p(m!) = \sum_{i \ge 1}\left\lfloor \frac{m}{p^i}\right\rfloor$$

(among $1, \ldots, m$ there are exactly $\lfloor m/p^i\rfloor$ multiples of $p^i$, and a number whose $p$-exponent is exactly $e$ gets counted $e$ times, for $i = 1,\ldots,e$). Therefore

$$v_p(C) = \sum_{i\ge1}\left(\left\lfloor\frac{2n}{p^i}\right\rfloor - 2\left\lfloor\frac{n}{p^i}\right\rfloor\right).$$

Writing a real number $t$ as $t = \lfloor t\rfloor + \theta$ with $0 \le \theta < 1$, we get $\lfloor 2t\rfloor - 2\lfloor t\rfloor = \lfloor 2\theta\rfloor \in \{0, 1\}$, so each term of the sum is $0$ or $1$. Moreover, when $p^i > 2n$ both floors vanish and the term disappears. Hence $v_p(C)$ is at most the number of $i$ with $p^i \le 2n$, and consequently

$$p^{v_p(C)} \le 2n$$

Also, a prime dividing $C$ divides $(2n)!$, so $p \le 2n$. By Theorem 4.2 we may factor $C = \prod_{p \le 2n} p^{v_p(C)}$, whence

$$C = \prod_{p\le 2n} p^{v_p(C)} \le (2n)^{\pi(2n)}.$$

Step 3: compare the two. Steps 1 and 2 give $(2n)^{\pi(2n)} \ge 4^n/(2n+1)$. Taking logarithms,

$$\pi(2n)\log(2n) \ \ge\ 2n\log 2 - \log(2n+1),$$

that is

$$\frac{\pi(2n)\log(2n)}{2n} \ \ge\ \log 2 - \frac{\log(2n+1)}{2n}.$$

As $n \to \infty$ the right-hand side converges to $\log 2$.

Finally we pass to real $x \to \infty$. For $x \ge 4$ put $n = \lfloor x/2\rfloor$, so that $2n \le x < 2n + 2$. Since $\pi$ is nondecreasing we have $\pi(x) \ge \pi(2n)$, and

$$\frac{\pi(x)\log x}{x} \ \ge\ \frac{\pi(2n)\log (2n)}{2n}\cdot\frac{2n}{x} \ \ge\ \left(\log 2 - \frac{\log(2n+1)}{2n}\right)\cdot\frac{x-2}{x}$$

(using $\log x \ge \log 2n$ and $2n > x - 2$). As $x\to\infty$ the right side tends to $\log 2$, giving the assertion about the $\liminf$.

∎

6. The prime number theorem

Definition 6.1（Logarithmic integral）

For $x > 1$ the logarithmic integral is defined by

$$\mathrm{li}(x) = \lim_{\varepsilon \to 0+}\left(\int_0^{1-\varepsilon}\frac{dt}{\log t} + \int_{1+\varepsilon}^{x}\frac{dt}{\log t}\right)$$

(the principal value at $t = 1$). Repeated integration by parts yields the asymptotic expansion

$$\mathrm{li}(x) = \frac{x}{\log x} + \frac{x}{(\log x)^2} + \frac{2x}{(\log x)^3} + \cdots$$

and in particular $\mathrm{li}(x) \sim x/\log x$.

Theorem 6.2（Prime number theorem）

$$\pi(x) \sim \frac{x}{\log x} \qquad (x \to \infty),$$

that is, $\lim_{x\to\infty}\dfrac{\pi(x)\log x}{x} = 1$. Equivalently, $\pi(x)\sim \mathrm{li}(x)$.

Remark 6.3（On the proof）

A proof of the prime number theorem lies beyond the scope of this article. The heart of the first proof, given in 1896 by Hadamard and de la Vallée Poussin, is to show that the Riemann zeta function

$$\zeta(s) = \sum_{n=1}^{\infty}\frac{1}{n^{s}} = \prod_{p}\left(1 - \frac{1}{p^{s}}\right)^{-1} \qquad (\operatorname{Re} s > 1)$$

has no zero on the line $\operatorname{Re} s = 1$. The Euler product (the second equality above, Theorem 3.1［リーマン予想とは何か］) follows by exactly the argument of Step 2 of Theorem 5.2, that is, from Theorem 4.2. The prime number theorem and the statement "$\zeta(1+it)\ne0$" are in fact known to be equivalent. In modern terms there is a short proof due to Newman, whose three-page exposition by Zagier is very readable. In 1949 Erdős and Selberg gave an elementary proof avoiding complex analysis (elementary does not mean easy). The zeta-function side of the story is treated in What Is the Riemann Hypothesis.

The content of the prime number theorem is easiest to grasp through the probabilistic reading “an integer near $n$ is prime with probability about $1/\log n$”. Indeed $\int_2^x dt/\log t$ is nothing but the integral of this density. Near $x = 10^{10}$ we have $1/\log(10^{10}) \approx 1/23.0 \approx 4.3\%$, so roughly $4$ out of every $100$ integers there are prime.

Let us check this numerically.

$x$	$\pi(x)$	$x/\log x$	$\pi(x)\big/\frac{x}{\log x}$	$\mathrm{li}(x)$	$\mathrm{li}(x)-\pi(x)$
$10^{3}$	168	144.8	1.161	178	10
$10^{4}$	1 229	1 085.7	1.132	1 246	17
$10^{5}$	9 592	8 685.9	1.104	9 630	38
$10^{6}$	78 498	72 382.4	1.084	78 628	130
$10^{7}$	664 579	620 420.7	1.071	664 918	339
$10^{8}$	5 761 455	5 428 681.0	1.061	5 762 209	754
$10^{9}$	50 847 534	48 254 942.4	1.054	50 849 235	1 701
$10^{10}$	455 052 511	434 294 481.9	1.048	455 055 615	3 104

The fourth column does tend to $1$, but even at $x = 10^{10}$ it is still off by $4.8\%$. This is no accident. The asymptotic expansion in Definition 6.1 gives $\mathrm{li}(x) - x/\log x \approx x/(\log x)^2$, so the error in the ratio decreases at a rate of order $1/\log x$. At $x = 10^{10}$ this is $1/\log x \approx 0.043$, in good agreement with the observed $0.048$. The sixth column, by contrast, shows a difference from $\mathrm{li}(x)$ that is smaller than $\pi(x)$ itself by many orders of magnitude, which shows that $\mathrm{li}(x)$ is a far better approximation.

The ratio of π(x) to x/log x. It approaches 1, but only at speed 1/log x (the horizontal axis is the common logarithm of x)

Example 6.4（Counting $\pi(10^6)$ with the sieve of Eratosthenes）

The values in the table can be verified directly. The following code uses only the standard library.

def sieve(n):
    is_prime = bytearray([1]) * (n + 1)
    is_prime[0] = is_prime[1] = 0
    p = 2
    while p * p <= n:
        if is_prime[p]:
            # multiples of p below p*p are already struck out by a smaller prime factor
            is_prime[p * p :: p] = bytearray(len(range(p * p, n + 1, p)))
        p += 1
    return is_prime


import math

s = sieve(10**6)
pi = sum(s)
print(pi)                       # 78498
print(10**6 / math.log(10**6))  # 72382.41365054197
print(pi / (10**6 / math.log(10**6)))  # 1.0844...

Starting the inner elimination at $p^2$ is legitimate because any multiple $kp$ of $p$ with $k < p$, hence below $p^2$, has already been struck out through a prime factor of $k$ (Lemma 3.1). Stopping the outer loop at $p^2 \le n$ is legitimate because every composite $m \le n$ has a prime factor at most $\sqrt m \le \sqrt n$ (if $m = ab$ with $a \le b$ then $a \le \sqrt m$, and the least prime factor of $a$ is at most $a$).

Example 6.5（Arbitrarily long gaps between primes）

That primes appear on average with density $1/\log n$ does not mean they are spread out evenly. For $n \ge 2$ consider the $n-1$ consecutive integers

$$n! + 2,\ n! + 3,\ \ldots,\ n! + n$$

For $2 \le k \le n$ we have $k \mid n!$ and $k \mid k$, so $k \mid n! + k$; moreover $1 < k < n! + k$, so $n!+k$ is composite. Hence there exist $n-1$ consecutive composite integers. Since $n$ is arbitrary, the gaps between primes become arbitrarily large. For instance with $n = 10$ the nine numbers $3628802, \ldots, 3628810$ are consecutive composites (in reality primes occur in much shorter intervals near this point, but for an existence proof this suffices).

7. Open problems

The prime number theorem completely determines the distribution of primes on average. About the behaviour of individual primes, however, astonishingly little is known.

7.1. The twin prime conjecture

A pair of primes $(p, p+2)$ differing by $2$ is called a pair of twin primes: $(3,5), (5,7), (11,13), (17,19), (29,31), \ldots$.

Twin prime conjecture: there are infinitely many twin primes.

The heuristic count suggested by the prime number theorem (the Hardy–Littlewood conjecture) predicts that the number of twin prime pairs up to $x$ is $2C_2 \int_2^x dt/(\log t)^2$, where $C_2 = 0.6601\ldots$ is the twin prime constant; it matches numerical experiment well. Yet even infinitude is open.

Some things are known. In 1919 Brun proved that the sum of the reciprocals of the twin primes,

$$\left(\frac13+\frac15\right) + \left(\frac15+\frac17\right)+\left(\frac1{11}+\frac1{13}\right)+\cdots$$

converges (its value, Brun’s constant, is estimated to be $1.902\ldots$). This contrasts with $\sum_p 1/p = \infty$ in Theorem 5.2 and means that twin primes are far rarer than primes in general. Note that convergence does not imply that there are only finitely many twin primes.

In 2013 Yitang Zhang proved that there are infinitely many pairs of primes differing by at most $7\times 10^{7}$ — the first finite bound for which infinitude could be established. Immediately afterwards Maynard and Tao independently gave different methods, and through the collaborative Polymath project the bound has been pushed down to $246$. Reaching $2$ is out of range for the present methods.

7.2. The Goldbach conjecture

The origin is a letter written by Goldbach to Euler in 1742.

(Strong) Goldbach conjecture: every even integer $\ge 4$ is a sum of two primes.

As in $4 = 2+2$, $6 = 3+3$, $8 = 3+5$, $100 = 3+97 = 11+89 = 17+83 = 29+71 = 41+59 = 47+53$, the number of representations grows with the number. Verification by computer has reached $4\times 10^{18}$, but there is no proof.

Weak Goldbach conjecture: every odd integer $\ge 7$ is a sum of three primes.

The weak conjecture follows from the strong one (for odd $n \ge 7$, $n - 3$ is an even number $\ge 4$). Vinogradov proved the weak conjecture for all sufficiently large odd numbers in 1937, and in 2013 Helfgott handled the remaining finitely many cases and announced a complete proof (formal publication has been a long process). As for the strong conjecture, Chen Jingrun showed in 1973 that every sufficiently large even number is the sum of a prime and a number that is either prime or a product of two primes.

7.3. The error term and the Riemann hypothesis

The prime number theorem says $\pi(x) \sim \mathrm{li}(x)$, but the size of the error $\pi(x) - \mathrm{li}(x)$ is not known in any definitive form. In 1901 von Koch showed that the Riemann hypothesis is equivalent to

$$\pi(x) = \mathrm{li}(x) + O\!\left(\sqrt{x}\,\log x\right)$$

(Theorem 6.3［リーマン予想とは何か］). In the table above one can see that $\mathrm{li}(x)-\pi(x)$ is consistently positive and stays of size about $\sqrt x$ (at $x = 10^{10}$ we have $\sqrt x = 10^5$ and the difference is $3104$).

“Consistently positive” does not last forever, however. In 1914 Littlewood proved that $\pi(x) - \mathrm{li}(x)$ changes sign infinitely often. The location of the first sign change is still not determined; only upper bounds (the estimates known as Skewes numbers) are available. The lesson of number theory here is that what the computations reveal is not the whole story.

8. Exercises

Exercise 8.1Easy

Prove that there are infinitely many primes of the form $4n+3$.

Solution

Suppose there were only finitely many primes of the form $4n+3$, say $p_1 = 3, p_2, \ldots, p_k$, and put

$$N = 4p_1p_2\cdots p_k - 1$$

Then $N \ge 4\cdot3 - 1 = 11 > 1$ and $N \equiv -1 \equiv 3 \pmod 4$.

Since $N$ is odd, all its prime factors are odd primes, hence of the form $4n+1$ or $4n+3$. If every prime factor were of the form $4n+1$, then since $(4a+1)(4b+1) = 4(4ab+a+b)+1$ the product would also be of the form $4n+1$, contradicting $N \equiv 3 \pmod 4$. Hence $N$ has a prime factor $q$ of the form $4n+3$ (existence of a prime factor is Lemma 3.1).

By assumption $q = p_i$ for some $i$. Then $q \mid 4p_1\cdots p_k$ and $q \mid N$, so $q \mid 4p_1\cdots p_k - N = 1$, contradicting $q \ge 3$. Therefore there are infinitely many primes of the form $4n+3$.

Infinitude also holds for primes of the form $4n+1$, but this elementary argument does not carry over as it stands; one needs the condition for $-1$ to be a quadratic residue mod $p$. See Congruences and Fermat’s Little Theorem for details.

Exercise 8.2Standard

Let $p_1 = 2 < p_2 = 3 < p_3 = 5 < \cdots$ be the primes in increasing order. Show that $\limsup_{n\to\infty}(p_{n+1} - p_n) = \infty$.

Solution

It suffices to show that for every $M \in \mathbb{N}$ there is an $n$ with $p_{n+1} - p_n > M$.

Put $N = (M+1)!$. By the same argument as in Example 6.5, the $M$ numbers $N + 2, N+3, \ldots, N + M + 1$ are all composite. Since $N + 1 \ge 3$, the set of primes not exceeding $N+1$ is nonempty and finite; let $p_n$ be its largest element, so $p_n \le N + 1$.

On the other hand $p_{n+1}$ is the least prime exceeding $N+1$, and since $N+2, \ldots, N+M+1$ are all composite we get $p_{n+1} \ge N + M + 2$. Hence

$$p_{n+1} - p_n \ge (N + M + 2) - (N+1) = M + 1 > M$$

As $M$ was arbitrary, $\limsup_{n\to\infty}(p_{n+1}-p_n) = \infty$.

Theorem 6.2 shows that the average gap is about $\log p_n$, but as this exercise shows, individual gaps become arbitrarily large.

Exercise 8.3Standard

Let $n$ be a positive integer. Show that if $2^n - 1$ is prime then $n$ is prime, and show by an explicit example that the converse fails.

Solution

We prove the contrapositive. Suppose $n$ is not prime. If $n = 1$ then $2^1 - 1 = 1$ is not prime. If $n$ is composite, write $n = ab$ with $1 < a < n$ and $1 < b < n$. Substituting $x = 2$ into the identity

$$x^{ab} - 1 = (x^{a} - 1)\left(x^{a(b-1)} + x^{a(b-2)} + \cdots + x^{a} + 1\right)$$

shows that $2^a - 1$ divides $2^n - 1$. From $a > 1$ we get $2^a - 1 \ge 3 > 1$, and from $a < n$ we get $2^a - 1 < 2^n - 1$. So $2^n-1$ has a divisor other than $1$ and itself, and by Definition 2.2 it is not prime.

The converse fails. Here $n = 11$ is prime, yet

$$2^{11} - 1 = 2047 = 23 \times 89$$

(indeed $23 \times 89 = 23\times 90 - 23 = 2070 - 23 = 2047$). Primes of the form $2^p - 1$ are called Mersenne primes; whether infinitely many exist is open.

Exercise 8.4Hard

Let $N$ be an integer with $N \ge 1$. Show that

$$\pi(N) \ \ge\ \frac{\log N}{2\log 2}$$

(an argument that yields a quantitative form of the infinitude of primes using unique factorization alone, without binomial coefficients).

Solution

Write each integer $n$ with $1 \le n \le N$ in the form $n = a b^{2}$, where $a$ is a squarefree positive integer and $b$ is a positive integer. Indeed, by Theorem 4.2 we may write $n = \prod_p p^{e_p}$ uniquely, so setting

$$b = \prod_p p^{\lfloor e_p/2\rfloor}, \qquad a = \prod_p p^{e_p - 2\lfloor e_p/2\rfloor}$$

each exponent in $a$ is $0$ or $1$, so $a$ is squarefree, and $ab^2 = n$.

Let us count the possibilities for $a$. The prime factors of $a$ are prime factors of $n \le N$, hence at most $N$, and each prime either occurs or does not, so there are at most $2^{\pi(N)}$ candidates for $a$. Next count $b$. From $b^2 \le n \le N$ we get $b \le \sqrt N$, so there are at most $\lfloor\sqrt N\rfloor \le \sqrt N$ candidates for $b$.

The assignment of $n$ to the pair $(a,b)$ is injective (since $n$ is recovered as $ab^2$), so

$$N \ \le\ 2^{\pi(N)}\sqrt{N}$$

Dividing by $\sqrt N$ gives $\sqrt N \le 2^{\pi(N)}$, and taking logarithms,

$$\frac{\log N}{2} \le \pi(N)\log 2, \qquad \text{that is}\qquad \pi(N) \ge \frac{\log N}{2\log 2}$$

This bound gives $\pi(N) \to \infty$ and so reproves the infinitude of primes, but compared with the true size $N/\log N$ it is overwhelmingly weak. Compare it with Proposition 5.3.

References

• G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008 — Chapter 1 (divisibility and primes), Chapter 2 (the distribution of primes), Chapter 22 (the distribution of primes, continued).
• Takagi Teiji, Shotō Seisūron Kōgi (Lectures on Elementary Number Theory), 2nd ed., Kyoritsu Shuppan, 1971 (in Japanese) — Chapter 1 (division of integers, greatest common divisors, prime factorization).
• T. M. Apostol, Introduction to Analytic Number Theory, Springer, 1976 — Chapter 3 (averages), Chapter 4 (Chebyshev’s functions and the prime number theorem).
• D. Zagier, “Newman’s short proof of the prime number theorem”, American Mathematical Monthly 104 (1997), 705–708 — the shortest modern presentation of the analytic proof of the prime number theorem.
• Y. Zhang, “Bounded gaps between primes”, Annals of Mathematics 179 (2014), 1121–1174.
• J. Maynard, “Small gaps between primes”, Annals of Mathematics 181 (2015), 383–413.

Appendix: proof of the Chebyshev upper bound

Goal. We prove the second half of Proposition 5.3, namely $\limsup_{x\to\infty}\pi(x)\log x/x \le \log 4$. The key is to estimate not the number of primes but the sum of their logarithms,

$$\theta(x) = \sum_{p \le x}\log p$$

(Chebyshev’s first function). Since $\theta(x) = \log\left(\prod_{p\le x} p\right)$, what follows is the same as the assertion that the product of the primes up to $x$ does not exceed $4^x$.

Step 1: $\prod_{p\le n} p \le 4^{n}$ for $n \ge 1$. We argue by strong induction on $n$. For $n = 1$ the left side is the empty product $1$ and the right side is $4$, so the claim holds. For $n = 2$ the left side is $2$ and the right side is $16$.

Let $n \ge 3$ and assume the claim for all positive integers below $n$. If $n$ is even, then since $n \ge 3$ it is not prime, so $\prod_{p\le n} p = \prod_{p \le n-1} p \le 4^{n-1} \le 4^{n}$.

If $n$ is odd, write $n = 2m+1$ with $m \ge 1$. Consider a prime $p$ with $m + 1 < p \le 2m+1$. Such a $p$ appears as a factor of $(2m+1)!$, while $p > m+1$ means it divides neither $m!$ nor $(m+1)!$. Hence

$$\binom{2m+1}{m} = \frac{(2m+1)!}{m!\,(m+1)!}$$

is divisible by $p$ (by Lemma 4.1, a prime dividing the numerator but not the denominator survives into the quotient). Combining this over distinct primes (again by Theorem 4.2),

$$\prod_{m+1 < p \le 2m+1} p \ \Bigm|\ \binom{2m+1}{m}, \qquad\text{hence}\qquad \prod_{m+1<p\le 2m+1} p \ \le\ \binom{2m+1}{m}.$$

Moreover $\binom{2m+1}{m} = \binom{2m+1}{m+1}$, and these are two of the terms of $\sum_{k=0}^{2m+1}\binom{2m+1}{k} = 2^{2m+1}$, so

$$2\binom{2m+1}{m} \le 2^{2m+1}, \qquad \text{that is}\qquad \binom{2m+1}{m}\le 4^{m}.$$

Applying the inductive hypothesis to $m+1 < n$ gives $\prod_{p \le m+1} p \le 4^{m+1}$, whence

$$\prod_{p\le 2m+1} p = \left(\prod_{p\le m+1}p\right)\left(\prod_{m+1<p\le 2m+1}p\right) \le 4^{m+1}\cdot 4^{m} = 4^{2m+1} = 4^{n}$$

which completes the induction. For real $x \ge 1$ we get $\theta(x) = \theta(\lfloor x\rfloor) \le \lfloor x\rfloor \log 4 \le x\log 4$.

Step 2: from $\theta$ to $\pi$. Let $1 < y < x$. For each prime $p$ with $y < p \le x$ we have $\log p > \log y$, so

$$\theta(x) \ \ge\ \sum_{y < p \le x}\log p \ >\ (\pi(x) - \pi(y))\log y$$

Since $\pi(y) \le y$ is a trivial bound (the primes up to $y$ form part of the positive integers up to $y$),

$$\pi(x) \ <\ \pi(y) + \frac{\theta(x)}{\log y} \ \le\ y + \frac{x\log 4}{\log y}.$$

Step 3: choosing $y$. Take $y = x/(\log x)^{2}$ (for $x$ large enough, $1 < y < x$). Then $\log y = \log x - 2\log\log x$, so

$$\frac{\pi(x)\log x}{x} \ <\ \frac{1}{\log x} + \frac{\log 4}{1 - \dfrac{2\log\log x}{\log x}}.$$

As $x \to \infty$ we have $\log\log x/\log x \to 0$, so the right side converges to $\log 4$. Hence $\limsup_{x\to\infty}\pi(x)\log x/x \le \log 4$.

Summary. The lower bound $\log 2 = 0.693\ldots$ and the upper bound $\log 4 = 1.386\ldots$ of Proposition 5.3 do indeed straddle the value $1$ asserted by Theorem 6.2. Chebyshev refined arguments of this kind as far as $0.921 < \pi(x)\log x/x < 1.106$ for sufficiently large $x$, but that the limit is exactly $1$ cannot be obtained from this direction. That is where the zeta function becomes necessary — the heart of the story of the prime number theorem.