Counting Primes: From Eratosthenes to Chebyshev - The Distribution of Primes Course

Primes: The Atoms of Arithmetic

Definitions and First Examples

Definition. An integer $ n > 1 $ is prime if its only positive divisors are 1 and $ n $ itself. An integer $ n > 1 $ that is not prime is called composite.

The first few primes are $ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, \ldots $. Note that 2 is the unique even prime; every subsequent prime is odd. Primality is a multiplicative notion: it encodes the irreducibility of an integer under multiplication.

Definition. The prime-counting function $ \pi : \mathbb{R} \to \mathbb{N}_0 $ is defined by

$$ \pi(x) = \#\{p \le x : p \text{ is prime}\}. $$

Some values: $ \pi(10) = 4 $, $ \pi(100) = 25 $, $ \pi(1000) = 168 $, $ \pi(10^6) = 78{,}498 $, $ \pi(10^9) = 50{,}847{,}534 $.

The Fundamental Theorem of Arithmetic

Theorem (Fundamental Theorem of Arithmetic). Every integer $ n \geq 2 $ can be written as a product of primes, and this factorization is unique up to the order of the factors.

Proof.

Existence. We proceed by strong induction on $ n $. If $ n = 2 $ the claim is immediate since 2 is prime. Assume every integer $ 2 \leq k < n $ is a product of primes. If $ n $ is prime, we are done. Otherwise $ n = ab $ with $ 2 \leq a, b < n $, and by the induction hypothesis both $ a $ and $ b $ factor into primes, so their product gives a prime factorization of $ n $.

Uniqueness. Suppose $ n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s $ are two prime factorizations of $ n $. Since $ p_1 \mid q_1 q_2 \cdots q_s $ and $ p_1 $ is prime, Euclid’s lemma (if $ p \mid ab $ and $ p $ is prime then $ p \mid a $ or $ p \mid b $) gives $ p_1 \mid q_j $ for some $ j $. But $ q_j $ is prime, so $ p_1 = q_j $. Cancel $ p_1 = q_j $ from both sides and apply induction on $ r $.

The unit 1 is excluded by convention precisely so that this uniqueness holds: otherwise $ 6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = \ldots $ would give infinitely many factorizations.

There Are Infinitely Many Primes

Theorem (Euclid, c. 300 BCE). There are infinitely many primes.

Proof. Suppose for contradiction that the complete list of primes is $ p_1, p_2, \ldots, p_k $. Form the number

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

By the Fundamental Theorem, $ N $ has a prime divisor $ p $. Since $ p \mid N $ and $ p \mid p_1 p_2 \cdots p_k $, we get $ p \mid 1 $, which is impossible for a prime. This contradiction shows no finite list exhausts the primes.

This argument does not say that $ N $ itself is prime, only that it has a prime factor outside the given list.

Gauss’s Conjecture and the Logarithmic Density of Primes

Examining tables of primes, Gauss noticed around 1792 (he was fifteen years old) that the primes seemed to thin out in a very regular way:

Important: Gauss’s Observation (1792).
The probability that a “random” integer near $ x $ is prime is approximately $ 1/\ln x $. Equivalently,
$$ \pi(x) \approx \frac{x}{\ln x}. $$
More precisely, Gauss conjectured that $ \pi(x) $ is well approximated by the logarithmic integral
$$ \mathrm{Li}(x) = \int_2^x \frac{dt}{\ln t}. $$

The ratio $ \pi(x)\ln(x)/x $ oscillates around 1 as $ x $ grows but converges to 1. This is the Prime Number Theorem, proved analytically a century later.

[Image: The prime-counting function compared with x/ln(x) and Li(x) for x up to 1000]

The prime-counting function

Sieve of Eratosthenes

Elementary Estimates

Euler’s Proof That the Sum of Reciprocal Primes Diverges

The divergence of $ \sum 1/p $ is qualitatively stronger than mere infinitude of primes: it says primes are not too sparse.

Theorem (Euler, 1737).

$$ \sum_{p \text{ prime}} \frac{1}{p} = +\infty. $$

Proof. Assume for contradiction that $ \sum_p 1/p $ converges. Choose $ k $ so that $ \sum_{p > p_k} 1/p < 1/2 $. Let $ P = \{p_1, \ldots, p_k\} $ be the primes up to $ p_k $, and let $ Q $ be the set of positive integers whose prime factors all lie in $ P $ (the $ P $-smooth numbers). For any $ N $,

$$ \sum_{n=1}^{N} \frac{1}{n} \leq \sum_{n \in Q} \frac{1}{n} = \prod_{p \in P} \left(1 + \frac{1}{p} + \frac{1}{p^2} + \cdots\right) = \prod_{p \in P} \frac{1}{1-1/p} < \infty. $$

But $ \sum 1/n $ diverges, contradiction.

A cleaner analytic argument: take logarithms of the Euler product at $ s=1 $ to get $ \ln\zeta(s) = \sum_p \sum_{k\geq 1} p^{-ks}/k $. As $ s \to 1^+ $, $ \ln\zeta(s) \to +\infty $, while $ \sum_p \sum_{k \geq 2} p^{-ks}/k $ converges. Hence $ \sum_p p^{-s} \to +\infty $ as $ s \to 1^+ $, giving divergence of $ \sum 1/p $.

Chebyshev’s Functions

Two weighted counts of primes are central to analytic number theory.

Definition. The Chebyshev theta function and psi function are

$$ \theta(x) = \sum_{p \leq x} \ln p, \qquad \psi(x) = \sum_{p^k \leq x} \ln p = \sum_{n \leq x} \Lambda(n), $$

where the von Mangoldt function is

$$ \Lambda(n) = \begin{cases} \ln p & \text{if } n = p^k \text{ for some prime } p \text{ and } k \geq 1, \\ 0 & \text{otherwise.} \end{cases} $$

These functions satisfy $ \theta(x) \leq \psi(x) $ and $ \psi(x) – \theta(x) = O(\sqrt{x}) $, so $ \psi(x) \sim \theta(x) $. The Prime Number Theorem is equivalent to any of

$$ \pi(x) \sim \frac{x}{\ln x}, \qquad \theta(x) \sim x, \qquad \psi(x) \sim x. $$

Chebyshev’s Bounds

Theorem (Chebyshev, 1852). There exist absolute constants $ c_1, c_2 > 0 $ such that for all $ x \geq 2 $,

$$ c_1 \frac{x}{\ln x} \leq \pi(x) \leq c_2 \frac{x}{\ln x}. $$

One may take $ c_1 = \ln 2 $ and $ c_2 = 6\ln 2 $.

Proof sketch. Consider the central binomial coefficient $ \binom{2n}{n} = (2n)!/(n!)^2 $. On one hand, $ \binom{2n}{n} \leq 4^n $. On the other hand, every prime $ p $ in the range $ n < p \leq 2n $ divides $ \binom{2n}{n} $ (since $ p $ divides the numerator but not the denominator). This yields $ \theta(2n) – \theta(n) \leq n \ln 4 $. Summing a dyadic decomposition gives the upper bound for $ \theta $, hence for $ \pi $. The lower bound comes from the exact $ p $-adic valuation of $ \binom{2n}{n} $ being at least $ n\ln 2 $ in total.

Bertrand’s Postulate

Theorem (Bertrand-Chebyshev). For every integer $ n \geq 1 $ there exists a prime $ p $ with $ n < p \leq 2n $.

We give the elegant elementary proof due to Erdos (1932).

Proof. Let $ N = \binom{2n}{n} $. We claim $ N \geq 4^n/(2n+1) $ and obtain a contradiction if all primes lie outside $ (n, 2n] $.

Step 1: Lower bound. $ (1+1)^{2n} = \sum_{k=0}^{2n}\binom{2n}{k} $. Since $ \binom{2n}{n} $ is the largest term and there are $ 2n+1 $ terms,

$$ \binom{2n}{n} \geq \frac{4^n}{2n+1}. $$

Step 2: p-adic valuation. The exact power of a prime $ p $ dividing $ \binom{2n}{n} $ is

$$ \sum_{i=1}^{\infty}\bigl(\lfloor 2n/p^i\rfloor – 2\lfloor n/p^i\rfloor\bigr) \leq \log_p(2n), $$

since each term is 0 or 1 and there are at most $ \log_p(2n) $ nonzero terms.

Step 3: Contribution by size.

Primes $ p > 2n $: cannot divide $ \binom{2n}{n} $.
Primes $ p \in (n, 2n] $: each contributes exactly $ p^1 $.
Primes $ p \in (2n/3, n] $: contribute $ p^0 = 1 $ (the valuation is 0).
Primes $ p \leq \sqrt{2n} $: contribute at most $ (2n)^{1/2} $ each.
Primes $ p \in (\sqrt{2n}, 2n/3] $: contribute at most $ p \leq 2n/3 $.

Step 4: Assume no prime in $ (n, 2n] $. Then the product of all prime powers dividing $ \binom{2n}{n} $ is at most

$$ \underbrace{(2n)^{\sqrt{2n}}}_{\text{small primes}} \times \underbrace{\prod_{p \leq 2n/3} p}_{\text{using } \theta(2n/3) \leq 2n/3 \cdot \ln 4} \leq (2n)^{\sqrt{2n}} \cdot 4^{2n/3}. $$

For large enough $ n $, this is smaller than $ 4^n/(2n+1) $, the lower bound from Step 1. This contradiction shows a prime must exist in $ (n, 2n] $.

For small $ n $ one checks directly: $ 2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631 $ witnesses the postulate for $ n \leq 316 $.

Mertens’ Theorems

Theorem (Mertens, 1874). Let $ \gamma \approx 0.5772 $ denote the Euler-Mascheroni constant. Then:

(i) $ \displaystyle\sum_{p \leq x} \frac{\ln p}{p} = \ln x + O(1). $

(ii) $ \displaystyle\sum_{p \leq x} \frac{1}{p} = \ln\ln x + M + O\!\left(\frac{1}{\ln x}\right), $ where $ M = \gamma + \sum_p \bigl[\ln(1-1/p)+1/p\bigr] \approx 0.2615 $.

(iii) $ \displaystyle\prod_{p \leq x}\!\left(1 – \frac{1}{p}\right) = \frac{e^{-\gamma}}{\ln x}\bigl(1 + O(1/\ln x)\bigr). $

Mertens’ third theorem quantifies how “rough” a random integer near $ x $ is. The product gives the density of integers coprime to all primes up to $ x $.

The Sieve of Eratosthenes

The oldest and most transparent sieve, credited to Eratosthenes of Cyrene (c. 276-194 BCE).

[Image: Sieve of Eratosthenes up to 100, with multiples of each prime eliminated in turn]

Algorithm. List integers $ 2, 3, \ldots, N $. Mark 2 prime, cross out all multiples of 2 exceeding 2. Mark the next unmarked number prime, cross out its multiples. Repeat until the smallest unmarked number exceeds $ \sqrt{N} $; all surviving numbers are prime.

Legendre’s version. If $ p_1, p_2, \ldots, p_r $ are the primes up to $ \sqrt{N} $, the inclusion-exclusion principle gives

$$ \pi(N) – \pi(\sqrt{N}) + 1 = \sum_{d \mid p_1 p_2 \cdots p_r} \mu(d) \left\lfloor \frac{N}{d}\right\rfloor, $$

where $ \mu $ is the Mobius function. This is exact but computationally expensive; the error from replacing $ \lfloor N/d\rfloor $ by $ N/d $ accumulates.

Brun’s Sieve and Twin Primes

Theorem (Brun, 1919). The sum $ \sum_{p:\,p+2 \text{ prime}} (1/p + 1/(p+2)) $ converges. Numerically, this Brun’s constant is $ B_2 \approx 1.9021605 $.

Brun’s proof uses a combinatorial truncation of the inclusion-exclusion formula. The key idea: use only a fixed number of terms in the Mobius sum, alternating to get upper and lower bounds. This gives

$$ \#\{p \leq x : p+2 \text{ prime}\} \leq C\frac{x}{\ln^2 x} $$

for an explicit constant $ C $. The convergence of Brun’s sum means that even if there are infinitely many twin primes, they are rare enough that the reciprocal sum converges, a stark contrast to all primes (where $ \sum 1/p $ diverges).

Selberg’s Sieve

In 1947, Selberg introduced a far more powerful sieve based on minimizing a quadratic form.

Setup. Let $ \mathcal{A} $ be a finite set of integers, $ P(z) = \prod_{p < z} p $, and let $ A_d = |\{a \in \mathcal{A} : d \mid a\}| $. Assume $ A_d \approx X\omega(d)/d $ for a multiplicative function $ \omega $.

Theorem (Selberg’s upper sieve).

$$ S(\mathcal{A}, z) \leq \frac{X}{G(z)} + O\!\left(z^2\right), $$

where $ G(z) = \sum_{\substack{d < z \\ d \mid P(z)}} \frac{\mu(d)^2}{\prod_{p\mid d}\omega(p)/(p-\omega(p))} $.

Applied to twin primes ($ \mathcal{A} = \{n(n+2) : n \leq x\} $, $ \omega(p) = 2 $ for $ p > 2 $), Selberg’s sieve gives the upper bound $ C \cdot x/\ln^2 x $ with an explicit constant $ C $.

Chen’s Theorem

Theorem (Chen Jingrun, 1973). Every sufficiently large even integer is the sum of a prime and a product of at most two primes (a prime or semiprime).

Chen’s proof uses Selberg’s upper sieve combined with the Jurkat-Richert lower sieve. This is the closest known approach to Goldbach’s conjecture and to showing infinitely many twin primes.

Exercises:

Use the Sieve of Eratosthenes to find all primes up to 120.

Verify Bertrand’s Postulate for $ n = 25 $ by finding a prime between 25 and 50.

Compute $ \sum_{p \leq 100} 1/p $ to two decimal places and compare with $ \ln\ln 100 + M $ where $ M \approx 0.2615 $.

Prove that the product $ \prod_{p \leq x}(1 – 1/p) $ tends to 0 as $ x \to \infty $. What does this say about the density of integers with small prime factors?

Show that Chebyshev’s bounds imply there are at least $ 0.69 \cdot x/\ln x $ primes up to $ x $ and at most $ 4.16 \cdot x/\ln x $ primes up to $ x $.

The central binomial coefficient $ \binom{20}{10} = 184{,}756 $. Factor this into primes and verify that every prime between 10 and 20 divides it.

Twin primes up to 100 are: (3,5), (5,7), (11,13), (17,19), (29,31), (41,43), (59,61), (71,73). Compute Brun’s constant to one decimal place using just these pairs.