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

> From divisibility to Euclid's theorem and unique factorization, then Chebyshev-type bounds from binomial coefficients, the prime number theorem, and the open problems beyond it.
> https://rikai.mugen-giken.com/en/mathematics/number-theory/primes-and-prime-number-theorem

## 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](/en/mathematics/foundations/proof-techniques) 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 id="def-divisibility" title="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>

<Definition id="def-prime" title="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.
</Definition>

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 id="lem-division" title="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.
$$
</Lemma>

<Proof of="lem-division">
**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 <Ref to="mathematics/foundations/proof-techniques#ax-well-ordering" text="well-ordering" />. 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'$.
</Proof>

<Lemma id="lem-bezout" title="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}\}$.
</Lemma>

<Proof of="lem-bezout">
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 <Ref to="lem-division" /> 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 <Ref to="def-divisibility" /> we get $d_0 = \gcd(a,b) = d$.
</Proof>

<Aside type="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](/mathematics/algebra/rings-and-fields). Rewritten in the language of ideals, the statement is <Ref to="mathematics/algebra/ideals-and-quotient-rings#prop-pid-z-kx" />.
</Aside>

## 3. The infinitude of primes

<Lemma id="lem-least-prime-factor" title="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.
</Lemma>

<Proof of="lem-least-prime-factor">
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.
</Proof>

<Theorem id="thm-euclid" title="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.
</Theorem>

<Proof of="thm-euclid">
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 <Ref to="lem-least-prime-factor" />, $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.
</Proof>

<Example id="ex-30031" title="$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.
</Example>

## 4. The fundamental theorem of arithmetic

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

<Lemma id="lem-euclid-lemma" title="Euclid's lemma">
Let $p$ be prime and $a, b$ integers. If $p \mid ab$, then $p \mid a$ or $p \mid b$.
</Lemma>

<Proof of="lem-euclid-lemma">
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 <Ref to="def-prime" /> it equals $1$ or $p$. If $\gcd(p,a) = p$ then $p \mid a$, contrary to assumption, so $\gcd(p, a) = 1$. By <Ref to="lem-bezout" /> 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$.
</Proof>

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 id="thm-fta" title="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$.
</Theorem>

<Proof of="thm-fta">
**Existence.** We argue by strong induction on $n$ (<Ref to="mathematics/foundations/proof-techniques#thm-strong-induction" text="complete induction" />). 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$ (<Ref to="def-prime" />). 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 <Ref to="lem-euclid-lemma" /> 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.
</Proof>

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 id="ex-sqrt2" title="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, <Ref to="thm-fta" />. Without uniqueness the argument does not get off the ground. The classical proof using fractions in lowest terms is in <Ref to="mathematics/foundations/proof-techniques#thm-sqrt2" />.
</Example>

<Remark id="rem-nonunique" title="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 <Ref to="mathematics/number-theory/fermats-last-theorem#ex-z-sqrt-5" />). What makes uniqueness work in $\mathbb{Z}$ is <Ref to="lem-bezout" />, 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](/mathematics/number-theory/fermats-last-theorem).
</Remark>

<Figure caption="The logical skeleton of this article: from the division algorithm through unique factorization to the distribution of primes">
<Mermaid code={`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"]`} />
</Figure>

## 5. How numerous are the primes?

<Definition id="def-pi" title="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**.
</Definition>

<Theorem id="thm-euler-divergence" title="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.
</Theorem>

<Proof of="thm-euler-divergence">
**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 <Ref to="thm-fta" /> 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.
</Proof>

This theorem carries more information than <Ref to="thm-euclid" />. Since the sum of reciprocals of the squares converges, $\sum 1/n^2 = \pi^2/6$ (<Ref to="mathematics/number-theory/riemann-hypothesis#ex-zeta-two" text="the Basel problem" />), 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 id="prop-chebyshev" title="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.
</Proposition>

<Proof of="prop-chebyshev">
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 <Ref to="thm-fta" /> 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$.
</Proof>

## 6. The prime number theorem

<Definition id="def-li" title="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$.
</Definition>

<Theorem id="thm-pnt" title="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)$.
</Theorem>

<Remark id="rem-pnt-proof" title="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, <Ref to="mathematics/number-theory/riemann-hypothesis#thm-euler-product" />) follows by exactly the argument of Step 2 of <Ref to="thm-euler-divergence" />, that is, from <Ref to="thm-fta" />. 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](/mathematics/number-theory/riemann-hypothesis).
</Remark>

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 <Ref to="def-li" /> 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.

<Figure caption="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)">
<svg viewBox="0 0 720 360" width="100%" role="img" aria-label="The ratio of π(x) to x/log x decreasing slowly towards 1">
  <g stroke="currentColor" fill="none" stroke-width="1.4">
    <line x1="60" y1="20" x2="60" y2="310" />
    <line x1="60" y1="310" x2="706" y2="310" />
  </g>
  <g stroke="currentColor" fill="none" stroke-width="1" stroke-dasharray="5 5" opacity="0.55">
    <line x1="60" y1="284.5" x2="706" y2="284.5" />
  </g>
  <polyline fill="none" stroke="var(--sl-color-accent)" stroke-width="2.5"
    points="60,79.7 150,116.6 240,152.2 330,177.6 420,194.2 510,206.9 600,215.8 690,223.5" />
  <g fill="var(--sl-color-accent)">
    <circle cx="60" cy="79.7" r="4" />
    <circle cx="150" cy="116.6" r="4" />
    <circle cx="240" cy="152.2" r="4" />
    <circle cx="330" cy="177.6" r="4" />
    <circle cx="420" cy="194.2" r="4" />
    <circle cx="510" cy="206.9" r="4" />
    <circle cx="600" cy="215.8" r="4" />
    <circle cx="690" cy="223.5" r="4" />
  </g>
  <g fill="currentColor" font-size="13" text-anchor="end">
    <text x="52" y="34">1.20</text>
    <text x="52" y="97.6">1.15</text>
    <text x="52" y="161.3">1.10</text>
    <text x="52" y="224.9">1.05</text>
    <text x="52" y="288.5">1.00</text>
  </g>
  <g fill="currentColor" font-size="13" text-anchor="middle">
    <text x="60" y="330">10³</text>
    <text x="150" y="330">10⁴</text>
    <text x="240" y="330">10⁵</text>
    <text x="330" y="330">10⁶</text>
    <text x="420" y="330">10⁷</text>
    <text x="510" y="330">10⁸</text>
    <text x="600" y="330">10⁹</text>
    <text x="690" y="330">10¹⁰</text>
  </g>
  <text x="60" y="352" fill="currentColor" font-size="13" text-anchor="start">x</text>
  <text x="66" y="16" fill="currentColor" font-size="13" text-anchor="start">π(x) ÷ (x / log x)</text>
</svg>
</Figure>

<Example id="ex-sieve" title="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.

```python
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$ (<Ref to="lem-least-prime-factor" />). 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>

<Example id="ex-prime-gaps" title="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).
</Example>

## 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 <Ref to="thm-euler-divergence" /> 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)
$$
(<Ref to="mathematics/number-theory/riemann-hypothesis#thm-von-koch" />). 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 id="exr-4n3" difficulty="Easy">
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 <Ref to="lem-least-prime-factor" />).

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](/en/mathematics/number-theory/congruences-and-fermat) for details.
</Solution>
</Exercise>

<Exercise id="exr-gap-limsup" difficulty="Standard">
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 <Ref to="ex-prime-gaps" />, 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$.

<Ref to="thm-pnt" /> shows that the average gap is about $\log p_n$, but as this exercise shows, individual gaps become arbitrarily large.
</Solution>
</Exercise>

<Exercise id="exr-mersenne" difficulty="Standard">
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 <Ref to="def-prime" /> 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.
</Solution>
</Exercise>

<Exercise id="exr-squarefree-bound" difficulty="Hard">
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 <Ref to="thm-fta" /> 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 <Ref to="prop-chebyshev" />.
</Solution>
</Exercise>

## 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 <Ref to="prop-chebyshev" />, 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 <Ref to="lem-euclid-lemma" />, a prime dividing the numerator but not the denominator survives into the quotient). Combining this over distinct primes (again by <Ref to="thm-fta" />),
$$
\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 <Ref to="prop-chebyshev" /> do indeed straddle the value $1$ asserted by <Ref to="thm-pnt" />. 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.