21.01.02 · number-theory / elementary

Primes, the fundamental theorem of arithmetic, and the infinitude of primes

shipped3 tiersLean: none

Anchor (Master): Euclid c. 300 BCE *Elements* IX Prop. 20 (originator of the infinitude proof); Hardy-Wright 2008 *An Introduction to the Theory of Numbers* 6e (Oxford, revised Heath-Brown-Silverman-Wiles) §§I-II, XXII; Apostol 1976 *Introduction to Analytic Number Theory* §§1-2; Lang 2002 *Algebra* (Springer GTM 211, 3e) Ch. II §5; Tenenbaum 2015 *Introduction to Analytic and Probabilistic Number Theory* 3e (Cambridge UP) §I; Euler 1737 *Comm. Acad. Sci. Petropolitanae* 9 (analytic proof via Euler product); Furstenberg 1955 *Amer. Math. Monthly* 62 (topological proof)

Intuition Beginner

A prime number is a whole number larger than $1$ that cannot be split into two smaller whole-number factors. The number $7$ is prime: the only way to write it as a product of two positive whole numbers is $1 \times 7$ . The number $12$ is not prime: it splits as $3 \times 4$ , or as $2 \times 6$ , or as $2 \times 2 \times 3$ . Numbers that are not prime and larger than $1$ are called composite. The number $1$ is treated as neither prime nor composite, a convention chosen so that prime factorisations are unique.

The first few primes are $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$ . They get sparser as you walk up the number line, but they never stop. Between $100$ and $200$ there are $21$ primes; between $1000$ and $1100$ there are $16$ ; between $1 0^{6}$ and $1 0^{6} + 100$ there are $6$ . The thinning is gradual, not sudden.

Every whole number larger than $1$ can be built by multiplying primes together, and the recipe is essentially unique. The number $360$ breaks up as $2 \times 2 \times 2 \times 3 \times 3 \times 5$ , or compactly $2^{3} \times 3^{2} \times 5$ . No other multiset of primes multiplies to $360$ . This pattern — every whole number is a product of primes, in essentially one way — is the fundamental theorem of arithmetic.

There are infinitely many primes. Euclid proved this around $300$ BCE with a short and beautiful argument. Suppose you had a complete finite list $p_{1}, p_{2}, \dots, p_{n}$ of all the primes. Form the number $N = p_{1} \times p_{2} \times \dots \times p_{n} + 1$ . Dividing $N$ by any prime in your list leaves a remainder of $1$ , so none of those primes divides $N$ . Either $N$ is itself a prime not in your list, or $N$ has a prime factor not in your list. Either way, your list was incomplete. The list of primes cannot be finite.

Visual Beginner

A picture of a number-line grid from $1$ to $100$ , with primes highlighted in one colour and composites in another. The composite numbers form a regular thicket — multiples of $2$ on every other square, multiples of $3$ on every third, multiples of $5$ on every fifth — and what remains is the sieve of primes. Below the grid, an arrow points to the number $360$ with its prime tree branching out: $360 \to 2 \times 180 \to 2 \times 2 \times 90 \to 2 \times 2 \times 2 \times 45 \to 2 \times 2 \times 2 \times 3 \times 15 \to 2 \times 2 \times 2 \times 3 \times 3 \times 5$ .

The grid is the sieve of Eratosthenes, the oldest method for finding primes: cross out every multiple of $2$ except $2$ itself, then every multiple of $3$ except $3$ , and so on. What survives is the list of primes up to your chosen bound. The factor tree is the algorithm for unique factorisation: split repeatedly until every leaf is prime, and the multiset of leaves is the factorisation.

Worked example Beginner

Factor the number $1, 001$ into primes.

Step 1. Check divisibility by the smallest primes. The number $1, 001$ is odd, so $2$ does not divide it. The digit sum is $1 + 0 + 0 + 1 = 2$ , which is not a multiple of $3$ , so $3$ does not divide it. The last digit is $1$ , not $0$ or $5$ , so $5$ does not divide it.

Step 2. Try $7$ . Compute $1, 001/7 = 143$ . The division comes out exactly: $7 \times 143 = 1, 001$ . So $1, 001 = 7 \times 143$ .

Step 3. Factor $143$ . Check $7$ : $143/7 = 20.43 \dots$ , not exact. Try $11$ : $11 \times 13 = 143$ , exact. So $143 = 11 \times 13$ .

Step 4. Both $11$ and $13$ are prime (no smaller prime divides them). The full factorisation is $1, 001 = 7 \times 11 \times 13$ .

What this tells us: even a small-looking number can have a memorable prime structure. The product $7 \times 11 \times 13 = 1, 001$ is the reason that multiplying any three-digit number by $1, 001$ produces a six-digit number with the original three digits repeated.

Check your understanding Beginner

Formal definition Intermediate+

The notion of a prime, the multiplicative structure of $Z$ , and the infinitude of primes admit clean definitions on the ring of integers, building on the divisibility and Bézout apparatus of 21.01.01.

Definition (prime). A positive integer $p > 1$ is prime if its only positive divisors are $1$ and $p$ . A positive integer $n > 1$ that is not prime is composite.

Definition (irreducible vs. prime, ring-theoretic). In an arbitrary integral domain $R$ , a nonzero non-unit $r \in R$ is irreducible if $r = ab$ forces $a$ or $b$ to be a unit; it is prime if $r ∣ ab$ forces $r ∣ a$ or $r ∣ b$ . In $Z$ the two notions coincide, because $Z$ is a unique-factorisation domain; in general rings they can differ.

Definition (prime factorisation). A prime factorisation of an integer $n \geq 2$ is an expression $n = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{k}^{a_{k}}$ with $p_{1} < p_{2} < \dots < p_{k}$ primes and $a_{i} \geq 1$ integers.

Definition (prime-counting function). The prime-counting function $π : R_{> 0} \to Z_{\geq 0}$ is defined by $$ \pi(x) = #{ p \leq x : p \text{ prime} }. $$ Thus $π (10) = 4$ (primes $2, 3, 5, 7$ ); $π (100) = 25$ ; $π (1000) = 168$ ; $π (1 0^{6}) = 78, 498$ .

Definition (sieve of Eratosthenes). Given a bound $N \geq 2$ , the sieve of Eratosthenes computes ${p : p \leq N, p prime}$ as follows: initialise the list $L = {2, 3, 4, \dots, N}$ ; for each $p$ from $2$ up to $⌊ N ⌋$ , if $p \in L$ , remove every multiple $2 p, 3 p, 4 p, \dots$ of $p$ from $L$ ; the remaining elements of $L$ are the primes up to $N$ .

Counterexamples to common slips

" $1$ is prime." The number $1$ is excluded from the primes by convention, because including it would break the uniqueness clause of the fundamental theorem: $6 = 2 \times 3 = 1 \times 2 \times 3 = 1 \times 1 \times 2 \times 3$ would give infinitely many "factorisations". The same convention extends to general unique-factorisation domains: units are factored out, leaving only the prime (irreducible) factors.
"Every irreducible element is prime." True in $Z$ and in every unique-factorisation domain, but false in general. In $Z [- 5]$ the element $2$ is irreducible (no smaller-norm factor) but not prime: $2 ∣ 6 = (1 + - 5) (1 - - 5)$ , yet $2$ divides neither factor. This is exactly the failure that motivated Dedekind's theory of ideals.
"Composites have more than one prime factorisation." The decomposition $12 = 2 \times 2 \times 3 = 2^{2} \times 3$ is the same factorisation written two ways. Uniqueness in the fundamental theorem means the multiset of prime factors (equivalently, the function $p \mapsto a_{p}$ recording the exponent of each prime) is unique.

Key theorem with proof Intermediate+

The signature theorem of this unit is the fundamental theorem of arithmetic. We prove both halves — existence via strong induction, uniqueness via Euclid's Lemma — and along the way state Euclid's original infinitude proof.

Theorem (fundamental theorem of arithmetic). Every integer $n \geq 2$ admits a prime factorisation $n = p_{1}^{a_{1}} \dots p_{k}^{a_{k}}$ with $p_{1} < p_{2} < \dots < p_{k}$ primes and $a_{i} \geq 1$ . The factorisation is unique: the multiset ${(p_{i}, a_{i})}$ is determined by $n$ .

Proof. Existence. By strong induction on $n \geq 2$ (the induction principle of 00.12.01). For $n = 2$ , the factorisation is $n = 2$ . For the inductive step, assume every integer $m$ with $2 \leq m < n$ admits a prime factorisation, and consider $n$ . If $n$ is prime, $n = n$ is the factorisation. Otherwise $n$ is composite, so $n = ab$ for some integers $a, b$ with $2 \leq a, b < n$ . By the inductive hypothesis, $a = p_{1} \dots p_{r}$ and $b = q_{1} \dots q_{s}$ as products of primes; concatenating, $n = p_{1} \dots p_{r} q_{1} \dots q_{s}$ is a product of primes. Re-grouping equal primes and sorting yields the canonical form.

Uniqueness. Suppose $n$ has two prime factorisations $n = p_{1} p_{2} \dots p_{r} = q_{1} q_{2} \dots q_{s}$ with all $p_{i}, q_{j}$ prime (writing the factorisations as flat products without exponent compression). We show by induction on $r$ that the two multisets coincide.

The base case $r = 1$ gives $p_{1} = q_{1} \dots q_{s}$ ; since $p_{1}$ is prime its only positive divisors are $1$ and $p_{1}$ , forcing $s = 1$ and $q_{1} = p_{1}$ .

For the inductive step, $p_{1} ∣ q_{1} q_{2} \dots q_{s}$ . By Euclid's Lemma (a prime dividing a product divides one of the factors — proved as Exercise 4 of 21.01.01 via Bézout), $p_{1} ∣ q_{j}$ for some $j$ . Since $q_{j}$ is prime and $p_{1} > 1$ , $p_{1} = q_{j}$ . Cancelling, $p_{2} \dots p_{r} = q_{1} \dots q_{j} \dots q_{s}$ , a product of $r - 1$ primes on the left. By the inductive hypothesis on $r - 1$ , the multisets ${p_{2}, \dots, p_{r}}$ and ${q_{1}, \dots, q_{j}, \dots, q_{s}}$ coincide. Adjoining $p_{1} = q_{j}$ to both sides gives the full multiset equality. $□$

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

Proof. Suppose for contradiction that $p_{1}, p_{2}, \dots, p_{n}$ is a complete enumeration of the primes. Form $N = p_{1} p_{2} \dots p_{n} + 1$ . By the fundamental theorem, $N \geq 2$ has at least one prime divisor $p$ . If $p = p_{i}$ for some $i$ , then $p ∣ N$ and $p ∣ p_{1} \dots p_{n}$ , so $p ∣ (N - p_{1} \dots p_{n}) = 1$ — impossible for a prime. Hence $p$ is a prime not in the list, contradicting completeness. $□$

Bridge. The fundamental theorem builds toward 01.02.07 polynomial rings + PIDs + UFDs, where the same statement reappears as " $Z$ is a unique-factorisation domain", and the proof generalises directly to any Euclidean domain. The central insight is that Euclid's Lemma — proved via Bézout in 21.01.01 — is what converts existence-of-factorisation into uniqueness-of-factorisation. This is exactly the bridge from the additive structure of $Z$ (Bézout's identity, $Z$ as a PID) to the multiplicative structure (unique factorisation). The infinitude corollary appears again in 21.03.01 the Riemann zeta function, where Euler's product $ζ (s) = \prod_{p} (1 - p^{- s})^{- 1}$ is the analytic encoding of unique factorisation; the divergence of $\sum 1/ p$ then forces the prime set to be infinite by a route independent of Euclid's combinatorial construction. The pattern generalises through Dirichlet 1837 on primes in arithmetic progressions and the Hadamard-de la Vallée Poussin 1896 prime number theorem to the entire modern apparatus of analytic number theory.

Exercises Intermediate+

Exercise 3 (medium, numeric).

Find the smallest prime gap greater than $10$ — that is, the smallest $n$ such that the difference between two consecutive primes at the start of $n$ exceeds $10$ .

Hint

List the primes and their successive gaps. The first few gaps after $2$ are $1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, \dots$ — keep scanning.

Answer

$113$ to $127$ , a gap of $14$ . Scanning consecutive primes: the gap pattern stays at most $8$ through $89$ to $97$ . At $113$ , the next prime is $127$ , gap $14$ — the first gap exceeding $10$ . (The first gap exceeding $8$ is also at $113$ , since $127 - 113 = 14 > 8$ . The first gap of exactly $10$ occurs much later, between $139$ and $149$ .) The growth of prime gaps is captured asymptotically by the prime number theorem: average gap near $x$ is about $ln x$ , so gaps of size $10$ become common around $x \sim e^{10} \approx 22, 000$ .

Exercise 5 (medium, symbolic).

Prove that $2$ is irrational by appealing directly to the fundamental theorem of arithmetic.

Hint

If $2 = p / q$ in lowest terms, then $p^{2} = 2 q^{2}$ . Compare the exponent of $2$ in the prime factorisations of both sides.

Answer

Suppose for contradiction $2 = p / q$ for some positive integers $p, q$ . Then $p^{2} = 2 q^{2}$ . Let $v_{2} : Z_{> 0} \to Z_{\geq 0}$ be the $2$ -adic valuation: $v_{2} (n)$ is the exponent of $2$ in the prime factorisation of $n$ . The valuation satisfies $v_{2} (ab) = v_{2} (a) + v_{2} (b)$ , an immediate consequence of unique factorisation.

Applying $v_{2}$ to $p^{2} = 2 q^{2}$ : $$ v_2(p^2) = 2 v_2(p), \qquad v_2(2 q^2) = v_2(2) + 2 v_2(q) = 1 + 2 v_2(q). $$

The left side $2 v_{2} (p)$ is even; the right side $1 + 2 v_{2} (q)$ is odd. They cannot be equal, contradiction. Hence no such $p, q$ exist, and $2$ is irrational.

Rubric: full credit for the parity argument on $v_{2}$ ; partial credit for the classical "even/odd" argument that does not invoke unique factorisation explicitly.

Exercise 7 (hard, symbolic).

A Mersenne prime is a prime of the form $M_{p} = 2^{p} - 1$ for some prime $p$ . Prove that if $2^{n} - 1$ is prime, then $n$ itself is prime.

Hint

Use the algebraic identity $2^{ab} - 1 = (2^{a} - 1) (2^{a (b - 1)} + 2^{a (b - 2)} + \dots + 2^{a} + 1)$ .

Answer

Suppose $n = ab$ is composite with $1 < a, b < n$ . The polynomial identity $$ x^{ab} - 1 = (x^a - 1)\left( x^{a(b-1)} + x^{a(b-2)} + \cdots + x^a + 1 \right) $$ holds for every $x$ (a finite-geometric-series identity). Setting $x = 2$ : $$ 2^n - 1 = (2^a - 1) \cdot \frac{2^n - 1}{2^a - 1} $$ with both factors at least $2^{a} - 1 \geq 2^{2} - 1 = 3$ and the second factor at least $2^{a} + 1 \geq 5$ . So $2^{n} - 1$ has a substantive factorisation, hence is not prime. The contrapositive: $2^{n} - 1$ prime $\Rightarrow n$ prime.

The converse fails: $2^{11} - 1 = 2047 = 23 \times 89$ , so $11$ is prime but $M_{11}$ is not. The known Mersenne primes (50 as of 2018) are the basis of the GIMPS distributed-computing search for record-large primes; the largest known prime as of writing is $M_{82, 589, 933}$ with $24, 862, 048$ decimal digits, found in 2018.

Rubric: full credit for the geometric-series identity and the factorisation argument; bonus for noting the converse fails and citing $M_{11}$ .

Exercise 8 (hard, symbolic).

A Fermat prime is a prime of the form $F_{n} = 2^{2^{n}} + 1$ . Prove that if $2^{k} + 1$ is prime for some integer $k \geq 1$ , then $k$ is a power of $2$ (so $2^{k} + 1$ is necessarily of Fermat form).

Hint

If $k$ has an odd factor $m > 1$ , write $k = m ℓ$ and use the identity $x^{m} + 1 = (x + 1) (x^{m - 1} - x^{m - 2} + \dots - x + 1)$ for odd $m$ .

Answer

Suppose $k$ has an odd factor $m > 1$ , say $k = m ℓ$ with $m \geq 3$ odd and $ℓ \geq 1$ . The identity $$ x^m + 1 = (x + 1)(x^{m-1} - x^{m-2} + x^{m-3} - \cdots - x + 1) $$ holds for odd $m$ (each pair of consecutive terms in the expansion of the right side cancels except the constant $+ 1$ ). Setting $x = 2^{ℓ}$ : $$ 2^k + 1 = 2^{m \ell} + 1 = (2^\ell)^m + 1 = (2^\ell + 1)\left((2^\ell)^{m-1} - (2^\ell)^{m-2} + \cdots + 1\right). $$ Both factors are at least $3$ (the first is $2^{ℓ} + 1 \geq 3$ ; the second has $m \geq 3$ terms each at least $1$ in absolute value, but its alternating-sum minimum is bounded below by $1$ since the leading term dominates: a careful estimate gives the second factor $\geq 2^{ℓ (m - 1)} - 2^{ℓ (m - 2)} = 2^{ℓ (m - 2)} (2^{ℓ} - 1) \geq 1$ , in fact at least $3$ once $ℓ \geq 1$ and $m \geq 3$ ). So $2^{k} + 1$ is composite, contrary to hypothesis.

Hence $k$ has no odd factor exceeding $1$ , i.e., $k$ is a power of $2$ .

The known Fermat primes are $F_{0} = 3, F_{1} = 5, F_{2} = 17, F_{3} = 257, F_{4} = 65537$ . Euler 1732 factored $F_{5} = 2^{32} + 1 = 641 \times 6, 700, 417$ , and no further Fermat primes are known. The Gauss-Wantzel theorem (Wantzel 1837) connects Fermat primes to constructible regular polygons: a regular $n$ -gon is constructible with compass-and-straightedge if and only if $n = 2^{k} p_{1} \dots p_{r}$ where the $p_{i}$ are distinct Fermat primes.

Rubric: full credit for the polynomial identity and the factorisation argument. Bonus for stating the connection to constructible polygons.

Lean formalization Intermediate+

Mathlib already supplies the primary objects of this unit: the predicate Nat.Prime, the multiset of prime factors Nat.factors, the finitely-supported function Nat.factorization, the fundamental-theorem statements Nat.factorization_prod_pow_eq_self and UniqueFactorizationMonoid.factors_prod, and the infinitude of primes via Nat.exists_infinite_primes.

-- Operative imports: Mathlib.Data.Nat.Prime, Mathlib.NumberTheory.Primes,
-- Mathlib.RingTheory.UniqueFactorizationDomain, Mathlib.Data.Nat.Factorization

#check @Nat.Prime
-- Nat.Prime : ℕ → Prop, defined as 2 ≤ p ∧ ∀ m, m ∣ p → m = 1 ∨ m = p

#check @Nat.exists_infinite_primes
-- Nat.exists_infinite_primes : ∀ (N : ℕ), ∃ p, N ≤ p ∧ Nat.Prime p

#check @Nat.factorization
-- Nat.factorization : ℕ →* (ℕ →₀ ℕ); the multiplicative homomorphism
-- assigning to each n its prime-exponent function

#check @Nat.factorization_prod_pow_eq_self
-- Nat.factorization_prod_pow_eq_self : ∀ {n : ℕ}, n ≠ 0 →
--   (n.factorization.prod fun p k => p ^ k) = n

#check @UniqueFactorizationMonoid.factors_prod
-- For any UFM, factoring then multiplying recovers the original (up to units)

The Lean module Codex.NumberTheory.Elementary.PrimesFTA will export Euclid's original proof (a finite-cardinality contradiction on $N = p_{1} \dots p_{n} + 1$ ) alongside the Mathlib Nat.exists_infinite_primes, and will record the fundamental theorem in the symmetric form n = p_1^{a_1} \cdots p_k^{a_k} with explicit decidability of the exponent function. The Mathlib gap discussed in the unit metadata (Chebyshev bounds, Mertens theorems, Furstenberg topology, Brun sieve, PNT) is the formalisation roadmap.

Advanced results Master

Theorem 1 (multiple proofs of the infinitude of primes). The proof attributed to Euclid c. 300 BCE Elements IX Prop. 20 ^[Euclid] is the canonical combinatorial argument: if $p_{1}, \dots, p_{n}$ exhausted the primes, then $N = p_{1} \dots p_{n} + 1$ would have a prime factor outside the list. The first analytic proof is due to Euler 1737 ^{[Euler 1737]}: the Euler product $$ \sum_{n=1}^\infty \frac{1}{n^s} ;=; \prod_p \frac{1}{1 - p^{-s}} \quad (s > 1) $$ encodes unique factorisation; letting $s \to 1^{+}$ the left side diverges as the harmonic series, so the right side — a product over primes — must have infinitely many factors. A topological proof was given by Furstenberg 1955 Amer. Math. Monthly 62 ^{[Furstenberg 1955]}: equip $Z$ with the topology generated by the arithmetic progressions $S (a, q) = {a + n q : n \in Z}$ for $q > 0$ ; each $S (a, q)$ is both open (by definition) and closed (as the complement of the union of the other $q - 1$ residue classes); since $Z ∖ {- 1, 1} = ⋃_{p} S (0, p)$ and a finite union of closed sets is closed but ${- 1, 1}$ is not open (every basic open set is infinite), the union must be infinite, hence the primes are infinite.

Theorem 2 (Chebyshev 1852 bounds). *There exist explicit positive constants $c_{1}, c_{2}$ with $c_{1} < 1 < c_{2}$ such that for all sufficiently large $x$ ,* $$ c_1 \cdot \frac{x}{\ln x} ;\leq; \pi(x) ;\leq; c_2 \cdot \frac{x}{\ln x}. $$ *Chebyshev's original values are $c_{1} = ln (2^{1/2} 3^{1/3} 5^{1/5} 3 0^{- 1/30}) \approx 0.92129$ and $c_{2} = (6/5) c_{1} \approx 1.10555$ * ^{[Chebyshev 1852]}. The proof uses elementary estimates on the central binomial coefficient $(n 2 n)$ : the factorisation $$ \binom{2n}{n} ;=; \prod_{p \leq 2n} p^{v_p(\binom{2n}{n})} $$ combined with Kummer's theorem on $v_{p}$ of binomial coefficients (the $p$ -adic valuation equals the number of carries in adding $n$ to itself in base $p$ ) gives both upper and lower bounds on $π (x)$ that scale as $x / ln x$ . Bertrand's postulate — for every $n \geq 1$ there is a prime in $(n, 2 n]$ — is an immediate consequence, since the Chebyshev lower bound forces $π (2 n) - π (n) > 0$ once $n$ is large, and small $n$ are verified by hand. Erdős 1932 Acta Litt. Sci. Szeged 5 gave a particularly clean elementary proof using the same Kummer-valuation machinery.

Theorem 3 (prime number theorem; Hadamard 1896, de la Vallée Poussin 1896). As $x \to \infty$ , $$ \pi(x) ;\sim; \frac{x}{\ln x}, \quad \text{equivalently} \quad \pi(x) \sim \mathrm{Li}(x) := \int_2^x \frac{dt}{\ln t}. $$ ^{[Hadamard 1896]} ^{[de la Vallée Poussin 1896]}. Both proofs proceed by showing that $ζ (s)$ has no zeros on the line $ℜ (s) = 1$ and then using a Tauberian argument to extract the asymptotic for $π (x)$ . de la Vallée Poussin obtained the quantitative form $π (x) = Li (x) + O (x exp (- c ln x))$ . The logarithmic-integral version $Li (x)$ is a closer approximation to $π (x)$ than $x / ln x$ : at $x = 1 0^{10}$ the error $π (x) - x / ln x \approx 2 \times 1 0^{7}$ while $π (x) - Li (x) \approx 3000$ . The elementary proof of the PNT (avoiding complex analysis) was achieved by Erdős and Selberg in 1948-49, settling a long-open question.

Theorem 4 (Mertens 1874). As $x \to \infty$ , $$ \sum_{p \leq x} \frac{\ln p}{p} ;=; \ln x + O(1), \qquad \sum_{p \leq x} \frac{1}{p} ;=; \ln \ln x + M + O!\left(\frac{1}{\ln x}\right), \qquad \prod_{p \leq x}\left(1 - \frac{1}{p}\right) \sim \frac{e^{-\gamma}}{\ln x}, $$ where $M = 0.2614972128 \dots$ is the Meissel-Mertens constant and $γ = 0.5772156649 \dots$ is the Euler-Mascheroni constant ^{[Mertens 1874]}. The three statements are equivalent given the PNT-grade asymptotics, but Mertens proved them by elementary techniques (Abel summation against Chebyshev-grade estimates) without needing the full PNT. The second statement implies in particular that $\sum_{p} 1/ p$ diverges — a stronger statement than infinitude — at the rate of an iterated logarithm. The third statement is the prime-product form, central to sieve theory.

Theorem 5 (Dirichlet 1837 on primes in arithmetic progressions). For every pair of coprime integers $a, q$ with $g cd (a, q) = 1$ , the arithmetic progression $a, a + q, a + 2 q, \dots$ contains infinitely many primes. Moreover, in a precise asymptotic sense the primes are equidistributed across the $φ (q)$ admissible residue classes mod $q$ : for each such class $$ \pi(x; q, a) := #{ p \leq x : p \equiv a \pmod q } ;\sim; \frac{1}{\varphi(q)} \cdot \pi(x), $$ ^{[Dirichlet 1837]}. Dirichlet's proof introduces the Dirichlet characters $χ : (Z / q Z)^{\times} \to C^{\times}$ and the associated $L$ -functions $L (s, χ) = \sum_{n} χ (n) / n^{s}$ ; the central step is to show that $L (1, χ) \neq = 0$ for every non-principal character $χ$ . This was the first proof in number theory to introduce systematic use of complex analytic functions and is the historical seed of modern analytic number theory. The quantitative equidistribution is the prime number theorem for arithmetic progressions, made effective by Siegel-Walfisz and culminating in the Bombieri-Vinogradov theorem of 1965.

Theorem 6 (Riemann hypothesis and its arithmetic content). Riemann's 1859 memoir Über die Anzahl der Primzahlen unter einer gegebenen Größe conjectured that all the non-real zeros of $ζ (s)$ lie on the line $ℜ (s) = 1/2$ (the critical line). The arithmetic equivalent is the error-term estimate $$ \big|\pi(x) - \mathrm{Li}(x)\big| ;=; O!\left(\sqrt{x} \ln x\right) \quad \text{as } x \to \infty. $$ The current state: Hardy 1914 proved infinitely many zeros lie on the critical line; Selberg 1942 showed a positive proportion do; Conrey 1989 raised this to $40%$ ; Bui-Conrey-Young 2011 to $41.05%$ . The hypothesis is one of the seven Clay Millennium Prize Problems and remains open as of writing. Numerical verification has confirmed all zeros below imaginary part $\approx 3 \times 1 0^{12}$ lie on the critical line (Gourdon 2004). Conditional on RH, the PNT acquires the strongest possible error term and a wealth of arithmetic statements (e.g., explicit prime-gap bounds, the Lindelöf hypothesis on $∣ ζ (1/2 + i t) ∣$ ) become accessible.

Theorem 7 (twin primes; Polignac 1849, Zhang 2014, Maynard 2015). A twin prime is a prime $p$ with $p + 2$ also prime: $(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), \dots$ . de Polignac 1849 conjectured infinitely many such pairs, and more generally infinitely many prime pairs $(p, p + 2 k)$ for every positive integer $k$ . The Brun sieve (Brun 1919 ^{[Brun 1919]}) established the convergence $\sum_{p, p + 2 prime} (1/ p + 1/ (p + 2)) < \infty$ , defining Brun's constant $B_{2} \approx 1.902160583 \dots$ — an indirect signature that twin primes thin out faster than primes themselves. The first unconditional bounded-gap result was Zhang 2014 Annals of Math. 179 ^{[Zhang 2014]}, who proved $lim inf (p_{n + 1} - p_{n}) \leq 7 \times 1 0^{7}$ . Maynard 2015 Annals of Math. 181 ^{[Maynard 2015]} reduced the bound to $600$ via a modified Selberg sieve, and the subsequent Polymath8b collaboration drove it to $246$ . The twin prime conjecture itself ( $lim inf = 2$ ) and the de Polignac conjecture remain open.

Theorem 8 (RSA cryptosystem; Rivest-Shamir-Adleman 1978). The RSA public-key cryptosystem ^{[Rivest-Shamir-Adleman 1978]} is a direct application of the fundamental theorem of arithmetic combined with the asymptotic asymmetry between multiplication and factorisation. Setup: choose two large primes $p, q$ (typically $1024$ or $2048$ bits each); publish $N = pq$ and a public exponent $e$ coprime to $φ (N) = (p - 1) (q - 1)$ ; keep secret the private exponent $d = e^{- 1} (mod φ (N))$ , computed via the extended Euclidean algorithm of 21.01.01. Encryption: $C = M^{e} (mod N)$ ; decryption: $M = C^{d} (mod N)$ . Security: recovering $d$ from $(N, e)$ without knowing $p, q$ is conjecturally as hard as factoring $N$ . The best classical algorithm (general number field sieve, Pollard et al. 1993) factors $n$ -bit integers in $exp (O (n^{1/3} (ln n)^{2/3}))$ time — sub-exponential but super-polynomial. Shor 1994 showed factoring is polynomial-time on a quantum computer, prompting the ongoing transition to post-quantum cryptosystems (NIST PQC standards 2024).

Synthesis. The infinitude of primes is the foundational reason that the multiplicative structure of $Z$ is genuinely rich, and this is exactly the bridge from elementary arithmetic to analytic number theory. The central insight, present already in Euclid c. 300 BCE and made quantitative by Euler 1737, is that the Euler product $ζ (s) = \prod_{p} (1 - p^{- s})^{- 1}$ encodes the fundamental theorem of arithmetic into a single analytic identity; the divergence of $\sum 1/ p$ then forces infinitude by a route entirely different from Euclid's combinatorial $N + 1$ construction. The Chebyshev bounds 1852 quantify infinitude to $π (x) ≍ x / ln x$ , and the Hadamard-de la Vallée Poussin theorem 1896 sharpens $≍$ to $\sim$ . Putting these together with Mertens 1874 and Dirichlet 1837 identifies the apparent randomness of primes with a precise asymptotic structure controlled by the analytic behaviour of $ζ$ and the Dirichlet $L$ -functions.

The pattern generalises in multiple directions. The Chebotarev density theorem extends Dirichlet's equidistribution from $(Z / q Z)^{\times}$ to Galois groups of number-field extensions, identifying the primes with the conjugacy classes of $Gal (K / Q)$ . The Sato-Tate conjecture (Clozel-Harris-Shepherd-Barron-Taylor 2008-11) extends Dirichlet-style equidistribution to the eigenvalues of Frobenius on $ℓ$ -adic representations of elliptic curves. The Riemann hypothesis stretches across analytic number theory, finite-field zeta functions (Weil 1948-49, Deligne 1974), automorphic $L$ -functions (Langlands programme), and conjecturally beyond. The bridge is everywhere the same: the multiplicative structure of $Z$ , encoded in the fundamental theorem and the Euler product, is the analytic shadow of the additive structure encoded by Bézout's identity in 21.01.01.

The applied consequence is the RSA cryptosystem and its descendants: the same multiplicative structure that organises the analytic theory provides the computational asymmetry — easy multiplication, hard factorisation — that secures most modern digital communication. Modern post-quantum cryptography (lattice-based, code-based, isogeny-based) replaces this hardness with alternatives, but the elementary fact remains that the fundamental theorem of arithmetic underwrote half a century of cryptographic infrastructure.

Full proof set Master

Proposition 1 (Euler 1737 analytic proof of infinitude). The sum $\sum_{p} 1/ p$ over the primes diverges; in particular, the set of primes is infinite.

Proof. Consider the partial Euler product, for $s > 1$ a real parameter: $$ \prod_{p \leq x}\left(1 - p^{-s}\right)^{-1} ;=; \prod_{p \leq x} \sum_{k=0}^\infty p^{-ks} ;=; \sum_{n \in N_x} n^{-s}, $$ where $N_{x}$ is the set of positive integers whose prime factors are all at most $x$ (an application of the fundamental theorem: each $n \in N_{x}$ arises in exactly one way as a product $\prod p^{k_{p}}$ ). As $x \to \infty$ , $N_{x}$ exhausts $Z_{> 0}$ , so $$ \prod_{p}\left(1 - p^{-s}\right)^{-1} ;=; \sum_{n=1}^\infty n^{-s} ;=; \zeta(s). $$

Taking logarithms and using $- ln (1 - p^{- s}) = \sum_{k = 1}^{\infty} p^{- k s} / k = p^{- s} + O (p^{- 2 s})$ : $$ \ln \zeta(s) ;=; \sum_p p^{-s} + R(s), \qquad R(s) = \sum_p \sum_{k \geq 2} p^{-ks}/k. $$ The remainder $R (s)$ stays bounded as $s \to 1^{+}$ : comparing with $\sum_{n} n^{- 2 s} /2$ gives $R (s) \leq ζ (2 s) /2 < ζ (2) /2 < \infty$ . On the other hand, $ζ (s) \to \infty$ as $s \to 1^{+}$ (the harmonic series diverges), so $ln ζ (s) \to \infty$ . Subtracting the bounded $R (s)$ leaves $\sum_{p} p^{- s} \to \infty$ as $s \to 1^{+}$ . By Abel's theorem on monotone convergence of Dirichlet series, this forces $\sum_{p} 1/ p = \infty$ .

Since a convergent series of positive terms cannot have $\sum_{p} 1/ p = \infty$ , the set of primes contributing to the sum must be infinite. $□$

Proposition 2 (Furstenberg 1955 topological proof of infinitude). The primes are infinite.

Proof. Topologise $Z$ by declaring the basic open sets to be the arithmetic progressions $$ S(a, q) = { a + n q : n \in \mathbb{Z} } = a + q \mathbb{Z}, \qquad a \in \mathbb{Z}, \ q \in \mathbb{Z}_{> 0}. $$ Verify: every nonempty basic open set is infinite (since $∣ S (a, q) ∣ = \infty$ ); the intersection of two basic open sets is again a union of basic open sets (a Chinese-remainder argument); the topology is Hausdorff (given $x \neq = y$ , choose $q > ∣ x - y ∣$ and observe $S (x, q) \cap S (y, q) = \emptyset$ ).

Each basic open $S (a, q)$ is also closed: its complement is the union of the other $q - 1$ residue classes mod $q$ , each of which is itself a basic open set: $$ \mathbb{Z} \setminus S(a, q) ;=; \bigcup_{b = 0, \ b \neq a}^{q - 1} S(b, q). $$ A union of open sets is open, so the complement is open, hence $S (a, q)$ is closed.

Now observe $$ \mathbb{Z} \setminus {-1, 1} ;=; \bigcup_p S(0, p), $$ the union taken over all primes $p$ : every integer $n$ with $∣ n ∣ \geq 2$ has at least one prime divisor $p$ , and conversely each $S (0, p)$ is contained in $Z ∖ {- 1, 1}$ provided $p > 1$ .

If the primes were finite, the right side would be a finite union of closed sets, hence closed. Equivalently, ${- 1, 1}$ would be open. But the only open sets containing $1$ are unions of basic open sets $S (a, q)$ with $1 \in S (a, q)$ , and every such basic open set is infinite. So ${- 1, 1}$ , being finite and nonempty, cannot be open. Contradiction. $□$

Proposition 3 (Chebyshev 1852 upper bound). There exists a constant $c > 0$ such that $π (x) \leq c \cdot x / ln x$ for all $x \geq 2$ .

Proof. For an integer $n \geq 1$ consider the central binomial coefficient $$ \binom{2n}{n} ;=; \frac{(2n)!}{(n!)^2}. $$ On one hand, $(n 2 n) < 4^{n}$ (since $4^{n} = (1 + 1)^{2 n} = \sum_{k = 0}^{2 n} (k 2 n)$ and $(n 2 n)$ is the largest of these $2 n + 1$ terms).

On the other hand, Kummer's theorem (or direct factorial counting via Legendre's formula $v_{p} (n!) = \sum_{k \geq 1} ⌊ n / p^{k} ⌋$ ) gives $$ v_p\left(\binom{2n}{n}\right) ;=; \sum_{k \geq 1}\left( \left\lfloor \frac{2n}{p^k}\right\rfloor - 2 \left\lfloor \frac{n}{p^k}\right\rfloor \right) ;\leq; \log_p(2n). $$ The terms in the sum are each $0$ or $1$ , and they vanish for $p^{k} > 2 n$ ; so the total contribution is at most $⌊ lo g_{p} (2 n)⌋$ .

Combining: every prime $p$ with $n < p \leq 2 n$ divides $(n 2 n)$ exactly once (since $v_{p} ((n 2 n)) = 1$ in this range from the formula). Hence $$ \prod_{n < p \leq 2n} p ;\leq; \binom{2n}{n} ;<; 4^n. $$ Taking logarithms, $\sum_{n < p \leq 2 n} ln p < n ln 4$ . Summing this estimate over the dyadic ranges $(2^{i - 1}, 2^{i}]$ for $i = 1, 2, \dots, ⌊ lo g_{2} x ⌋$ : $$ \sum_{p \leq x} \ln p ;\leq; (\ln 4) \cdot x \cdot (1 + 1/2 + 1/4 + \cdots) ;=; 2 (\ln 4) \cdot x. $$ Equivalently $θ (x) := \sum_{p \leq x} ln p = O (x)$ .

Now extract $π (x)$ via Abel summation: $θ (x) \geq \sum_{x^{1/2} < p \leq x} ln p \geq \frac{1}{2} (ln x) \cdot (π (x) - π (x))$ . Rearranging, $π (x) \leq 2 θ (x) / ln x + π (x) \leq 2 θ (x) / ln x + x = O (x / ln x)$ . $□$

Proposition 4 (Bertrand's postulate, Erdős 1932 elementary form). For every integer $n \geq 1$ , the interval $(n, 2 n]$ contains a prime.

Proof. Assume for contradiction that $(n, 2 n]$ contains no prime. We derive an upper bound on $(n 2 n)$ that contradicts the lower bound $(n 2 n) \geq 4^{n} / (2 n + 1)$ for $n$ large.

By Proposition 3's Kummer estimate, $v_{p} ((n 2 n)) \leq lo g_{p} (2 n)$ for every prime $p \leq 2 n$ , with equality on at most one factor of $p^{l o g_{p} (2 n)} \leq 2 n$ . So $$ \binom{2n}{n} ;=; \prod_{p \leq 2n} p^{v_p(\binom{2n}{n})} ;\leq; \prod_{p \leq \sqrt{2n}} (2n) \cdot \prod_{\sqrt{2n} < p \leq 2n/3} p \cdot \prod_{n < p \leq 2n} p. $$ The middle range follows from a refined Kummer estimate showing $v_{p} ((n 2 n)) = 0$ for $2 n /3 < p \leq n$ when $n \geq 3$ . The third range is assumed empty by the contradiction hypothesis. Using $\prod_{p \leq y} p \leq 4^{y}$ (a separate elementary lemma, also proved by induction on $y$ via the central-binomial trick), the middle factor is at most $4^{2 n /3}$ .

Bounding: $(n 2 n) \leq (2 n)^{2 n} \cdot 4^{2 n /3}$ . Comparing with the lower bound $4^{n} / (2 n + 1)$ : $$ \frac{4^n}{2n+1} ;\leq; (2n)^{\sqrt{2n}} \cdot 4^{2n/3} \quad \Longleftrightarrow \quad 4^{n/3} \leq (2n+1)(2n)^{\sqrt{2n}}. $$ The left side grows exponentially in $n$ ; the right side grows like $(2 n)^{2 n}$ , which is sub-exponential. The inequality fails for all $n \geq 468$ (a direct numerical check), giving a contradiction.

Bertrand for $n \leq 467$ is verified by exhibiting an explicit prime in each $(n, 2 n]$ . Erdős noticed that the chain of primes $2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631$ — each less than twice the previous — covers all $n \leq 467$ at once. $□$

Connections Master

Divisibility, GCD, Bézout's identity, and the Euclidean algorithm 21.01.01. Just shipped. Supplies Bézout and Euclid's Lemma — the latter is the load-bearing step in the uniqueness half of the fundamental theorem proved above (Key Theorem). The implication chain " $Z$ Euclidean $\Rightarrow$ $Z$ PID $\Rightarrow$ $Z$ UFD" of 21.01.01 Master tier is exactly the additive-to-multiplicative bridge: Bézout gives Euclid's Lemma gives unique factorisation. Without 21.01.01 the present unit's central theorem cannot be proved.
Polynomial rings, PIDs, and UFDs 01.02.07. Pending. The fundamental theorem of arithmetic generalises directly to the statement " $Z$ is a unique-factorisation domain". The same proof (existence via well-ordered descent, uniqueness via Euclid's Lemma) applies in $k [X]$ for $k$ a field, in $Z [i]$ , in $Z [ω]$ , and in every Euclidean domain. The chapter-closing synthesis appears in 01.02.07 (when shipped), where the abstract UFD framework will replace the ad-hoc $Z$ -specific arguments with the categorical statement.
Riemann zeta function and the Euler product 21.03.01. Shipped. The Euler product $ζ (s) = \prod_{p} (1 - p^{- s})^{- 1}$ is the analytic encoding of the fundamental theorem of arithmetic established in this unit. Euler's 1737 analytic proof of infinitude (Master Proposition 1) is the entry point. The full development of $ζ$ 's functional equation, its non-real zeros, and the Riemann hypothesis lives in 21.03.01; the present unit's Master Theorem 6 only states RH and its arithmetic-equivalent error bound, deferring the analytic apparatus.
Prime number theorem and Dirichlet density 21.03.04. Shipped (in the $_{u} nk n o w n /_{n} e w$ staging). The qualitative infinitude of primes proved here, quantified to $π (x) ≍ x / ln x$ by Chebyshev (Master Theorem 2), and sharpened to $π (x) \sim x / ln x$ by Hadamard-de la Vallée Poussin (Master Theorem 3). The proof of the PNT — via analytic continuation of $ζ (s)$ and the non-vanishing of $ζ (1 + i t)$ — lives in 21.03.04. The Dirichlet generalisation to arithmetic progressions (Master Theorem 5) is the bridge to L-functions developed in the same chapter.
Mathematical induction 00.12.01. Prerequisite. The existence half of the fundamental theorem is a strong-induction argument on $n \geq 2$ ; the well-ordering principle equivalent to strong induction is also the operational content of "every nonempty subset of $N$ has a least element", invoked in Euclid's argument and in the lower-bound proof of the Chebyshev estimates. The foundational reason that elementary number theory works as a self-contained subject is that $N$ is well-founded.

Historical & philosophical context Master

The infinitude of primes is the oldest result in number theory still in current use. Euclid c. 300 BCE Elements Book IX, Proposition 20 ^[Euclid] gives the argument in essentially its modern form: "prime numbers are more than any assigned multitude of prime numbers". The Greek formulation considers three primes and constructs a fourth; Euclid does not state the argument for an arbitrary finite list, but the structure is identical, and later commentators (notably Theon of Alexandria, fourth century CE) generalised it. The fundamental theorem of arithmetic — every positive integer is a unique product of primes — is implicit in Euclid VII.30 (Euclid's Lemma in the prime case) and VII.31 (existence of a prime divisor), but the explicit uniqueness statement seems to first appear in Gauss 1801 Disquisitiones Arithmeticae §16, Theorem 8: Compositum quemvis numerum modis unico in factores primos resolvi posse ("Every composite number can be resolved into prime factors in a unique way").

Euler 1737 Comm. Acad. Sci. Petropolitanae 9 ^{[Euler 1737]} initiated the analytic study of primes with the Euler product identity. The proof that $\sum_{p} 1/ p$ diverges is given in the same paper and constitutes the first proof of infinitude not modelled on Euclid's combinatorial $N + 1$ construction. Dirichlet 1837 ^{[Dirichlet 1837]} extended Euler's analytic technique from the identity character on $(Z / q Z)^{\times}$ to the full character group, proving the equidistribution of primes across coprime residue classes. The bridge from Euler-Dirichlet to the modern theory is the systematic identification of $\sum_{n} χ (n) / n^{s}$ with a complex-analytic object satisfying functional equations and admitting an analytic continuation; Riemann 1859 Monatsber. Berlin. Akad. identified the analytic apparatus needed and made the central conjecture that all non-real zeros of $ζ (s)$ have real part $1/2$ .

The prime number theorem $π (x) \sim x / ln x$ was conjectured by Gauss as a teenager (in correspondence with Encke, dated 1849 but referring to observations from 1792-1793) and independently by Legendre 1798 Essai sur la théorie des nombres. Chebyshev 1852 J. Math. Pures Appl. 17 ^{[Chebyshev 1852]} proved the first effective bounds via elementary combinatorial-binomial techniques and used them to confirm Bertrand's postulate. Hadamard 1896 Bull. Soc. Math. France 24 ^{[Hadamard 1896]} and de la Vallée Poussin 1896 Ann. Soc. Sci. Bruxelles 20 ^{[de la Vallée Poussin 1896]} independently proved the asymptotic, using complex-analytic techniques on $ζ (s)$ near the line $ℜ (s) = 1$ . Mertens 1874 J. reine angew. Math. 78 ^{[Mertens 1874]} had earlier proved the three constants-asymptotic statements that bear his name, via elementary Abel-summation arguments against the Chebyshev bounds.

The elementary proof of the prime number theorem (avoiding complex analysis) was achieved by Erdős and Selberg in 1948-49; both worked from a "fundamental inequality" of Selberg, $θ (x) ln x + \sum_{p \leq x} θ (x / p) ln p = 2 x ln x + O (x)$ , and reached the asymptotic via Tauberian-style manipulation in real-variable terms. The priority dispute between Erdős and Selberg was substantial — Selberg was awarded the 1950 Fields Medal in part for this work; Erdős received the 1951 Cole Prize. Furstenberg 1955 Amer. Math. Monthly 62 ^{[Furstenberg 1955]} gave the topological proof of infinitude as a one-page note; it has become a standard exhibit in introductory topology courses.

The twin prime conjecture (Polignac 1849) and the de Polignac generalisation remain open. Brun 1919 Bull. Sci. Math. 43 ^{[Brun 1919]} introduced the combinatorial sieve named for him and established the convergence of $\sum (1/ p + 1/ (p + 2))$ over twin primes, defining Brun's constant. Modern sieve theory descends from this work through Selberg 1950s, Bombieri-Vinogradov 1965, and the recent bounded-gap revolution: Zhang 2014 Annals 179 ^{[Zhang 2014]} established $lim inf (p_{n + 1} - p_{n}) \leq 7 \times 1 0^{7}$ ; Maynard 2015 Annals 181 ^{[Maynard 2015]} reduced the bound to $600$ via a modified Selberg-sieve weight; the Polymath8b collaboration drove the bound to $246$ . The Goldbach conjecture (Goldbach 1742, in correspondence with Euler) that every even integer $> 2$ is a sum of two primes remains open in its binary form; Helfgott 2013 proved the weak (ternary) Goldbach conjecture — every odd integer $> 5$ is a sum of three primes — unconditionally.

The applied legacy is dominated by Rivest-Shamir-Adleman 1978 CACM 21 ^{[Rivest-Shamir-Adleman 1978]}. RSA encrypted the bulk of internet commerce from the 1990s through the 2010s and remains in widespread use, with the security premise — factoring is computationally hard — resting on the fundamental theorem of arithmetic combined with the absence of efficient classical factoring algorithms. Shor 1994 FOCS 35 showed quantum computers can factor in polynomial time; the NIST post-quantum cryptography standardisation (initiated 2016, finalised 2024) replaces RSA-style cryptosystems with lattice-based and code-based alternatives whose security rests on different hardness assumptions, but the elementary number-theoretic groundwork laid by Euclid, Euler, Gauss, and Dirichlet remains the substrate for the entire field.

Bibliography Master

@book{EuclidElementsIX,
  author    = {Euclid},
  title     = {The Thirteen Books of Euclid's Elements},
  editor    = {Heath, Thomas L.},
  publisher = {Cambridge University Press},
  year      = {1908},
  note      = {Three volumes; Dover reprint 1956. Book IX Proposition 20 contains the infinitude-of-primes proof, originally c. 300 BCE.}
}

@article{Euler1737,
  author  = {Euler, Leonhard},
  title   = {Variae observationes circa series infinitas},
  journal = {Commentarii Academiae Scientiarum Imperialis Petropolitanae},
  volume  = {9},
  pages   = {160--188},
  year    = {1737}
}

@article{Bertrand1845,
  author  = {Bertrand, Joseph},
  title   = {M\'{e}moire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme},
  journal = {Journal de l'\'{E}cole Royale Polytechnique},
  volume  = {30},
  pages   = {123--140},
  year    = {1845}
}

@article{Chebyshev1852,
  author  = {Chebyshev, Pafnuty L.},
  title   = {M\'{e}moire sur les nombres premiers},
  journal = {Journal de Math\'{e}matiques Pures et Appliqu\'{e}es},
  volume  = {17},
  pages   = {366--390},
  year    = {1852}
}

@article{Dirichlet1837,
  author  = {Dirichlet, Peter Gustav Lejeune},
  title   = {Beweis des Satzes, da{\ss} jede unbegrenzte arithmetische Progression, deren erstes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Factor sind, unendlich viele Primzahlen enth\"{a}lt},
  journal = {Abhandlungen der K\"{o}niglichen Preussischen Akademie der Wissenschaften zu Berlin},
  pages   = {45--81},
  year    = {1837}
}

@article{Mertens1874,
  author  = {Mertens, Franz},
  title   = {Ein Beitrag zur analytischen Zahlentheorie},
  journal = {Journal f\"{u}r die reine und angewandte Mathematik},
  volume  = {78},
  pages   = {46--62},
  year    = {1874}
}

@article{Hadamard1896,
  author  = {Hadamard, Jacques},
  title   = {Sur la distribution des z\'{e}ros de la fonction $\zeta(s)$ et ses cons\'{e}quences arithm\'{e}tiques},
  journal = {Bulletin de la Soci\'{e}t\'{e} Math\'{e}matique de France},
  volume  = {24},
  pages   = {199--220},
  year    = {1896}
}

@article{ValleePoussin1896,
  author  = {de la Vall\'{e}e Poussin, Charles},
  title   = {Recherches analytiques sur la th\'{e}orie des nombres premiers},
  journal = {Annales de la Soci\'{e}t\'{e} Scientifique de Bruxelles},
  volume  = {20},
  pages   = {183--256},
  year    = {1896}
}

@article{Brun1919,
  author  = {Brun, Viggo},
  title   = {La s\'{e}rie $1/5 + 1/7 + 1/11 + \ldots$ o\`{u} les d\'{e}nominateurs sont nombres premiers jumeaux est convergente ou finie},
  journal = {Bulletin des Sciences Math\'{e}matiques},
  volume  = {43},
  pages   = {100--128},
  year    = {1919}
}

@article{Furstenberg1955,
  author  = {Furstenberg, Hillel},
  title   = {On the infinitude of primes},
  journal = {American Mathematical Monthly},
  volume  = {62},
  pages   = {353},
  year    = {1955}
}

@article{RivestShamirAdleman1978,
  author  = {Rivest, Ronald L. and Shamir, Adi and Adleman, Leonard},
  title   = {A method for obtaining digital signatures and public-key cryptosystems},
  journal = {Communications of the ACM},
  volume  = {21},
  pages   = {120--126},
  year    = {1978}
}

@article{Zhang2014,
  author  = {Zhang, Yitang},
  title   = {Bounded gaps between primes},
  journal = {Annals of Mathematics},
  volume  = {179},
  pages   = {1121--1174},
  year    = {2014}
}

@article{Maynard2015,
  author  = {Maynard, James},
  title   = {Small gaps between primes},
  journal = {Annals of Mathematics},
  volume  = {181},
  pages   = {383--413},
  year    = {2015}
}

@book{HardyWright2008,
  author    = {Hardy, G. H. and Wright, E. M.},
  title     = {An Introduction to the Theory of Numbers},
  edition   = {6},
  publisher = {Oxford University Press},
  year      = {2008},
  note      = {Revised by D. R. Heath-Brown and J. H. Silverman, foreword by A. Wiles. Chapters I-II and XXII contain the elementary and analytic material respectively.}
}

@book{Apostol1976,
  author    = {Apostol, Tom M.},
  title     = {Introduction to Analytic Number Theory},
  series    = {Undergraduate Texts in Mathematics},
  publisher = {Springer},
  year      = {1976}
}

@book{Tenenbaum2015,
  author    = {Tenenbaum, G\'{e}rald},
  title     = {Introduction to Analytic and Probabilistic Number Theory},
  edition   = {3},
  publisher = {Cambridge University Press},
  year      = {2015}
}

Prerequisites

21.01.01
00.12.01
00.01.01

Tier anchors

beginner: Burton 2010 *Elementary Number Theory* 7e §3 (primes, sieve of Eratosthenes, infinitude); Khan Academy 'prime factorisation' module
intermediate: Ireland-Rosen 1990 *A Classical Introduction to Modern Number Theory* (Springer GTM 84, 2e) §§1.1-1.3; Apostol 1976 *Introduction to Analytic Number Theory* §§1.4-1.7; Niven-Zuckerman-Montgomery 1991 *An Introduction to the Theory of Numbers* 5e Ch. 1-2
master: Euclid c. 300 BCE *Elements* IX Prop. 20 (originator of the infinitude proof); Hardy-Wright 2008 *An Introduction to the Theory of Numbers* 6e (Oxford, revised Heath-Brown-Silverman-Wiles) §§I-II, XXII; Apostol 1976 *Introduction to Analytic Number Theory* §§1-2; Lang 2002 *Algebra* (Springer GTM 211, 3e) Ch. II §5; Tenenbaum 2015 *Introduction to Analytic and Probabilistic Number Theory* 3e (Cambridge UP) §I; Euler 1737 *Comm. Acad. Sci. Petropolitanae* 9 (analytic proof via Euler product); Furstenberg 1955 *Amer. Math. Monthly* 62 (topological proof)

References

Euclid — Elements, Book IX · Proposition 20 (c. 300 BCE). Heath translation, *The Thirteen Books of Euclid's Elements*, Vol. 2, Cambridge University Press 1908; Dover reprint 1956. The earliest extant proof of the infinitude of primes, by reductio on a hypothetical finite list. Often phrased 'prime numbers are more than any assigned multitude of prime numbers'.
Euler, L. — Variae observationes circa series infinitas · *Commentarii Academiae Scientiarum Imperialis Petropolitanae* 9 (1737), 160-188. Introduces the Euler product $\sum 1/n^s = \prod_p (1 - p^{-s})^{-1}$ and uses the divergence of $\sum 1/p$ at $s = 1$ to give an analytic proof of the infinitude of primes.
Bertrand, J. — Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme · *Journal de l'École Royale Polytechnique* 30 (1845), 123-140. Conjectures Bertrand's postulate (a prime in every interval $(n, 2n]$); verified by Bertrand up to $n = 3{,}000{,}000$.
Chebyshev, P. L. — Mémoire sur les nombres premiers · *Journal de Mathématiques Pures et Appliquées* 17 (1852), 366-390. The first published proof of Bertrand's postulate, together with the Chebyshev bounds $0.92129 \cdot x/\ln x \leq \pi(x) \leq 1.10555 \cdot x/\ln x$ for sufficiently large $x$, derived from combinatorial identities on the central binomial coefficient $\binom{2n}{n}$.
Dirichlet, P. G. L. — Beweis des Satzes, daß jede unbegrenzte arithmetische Progression, deren erstes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Factor sind, unendlich viele Primzahlen enthält · *Abhandlungen der Königlichen Preussischen Akademie der Wissenschaften zu Berlin* (1837), 45-81. Proves that every arithmetic progression $a, a+q, a+2q, \ldots$ with $\gcd(a, q) = 1$ contains infinitely many primes, using the L-functions $L(s, \chi) = \sum_n \chi(n)/n^s$ for Dirichlet characters $\chi \pmod q$.
Mertens, F. — Ein Beitrag zur analytischen Zahlentheorie · *Journal für die reine und angewandte Mathematik* 78 (1874), 46-62. Proves the three Mertens theorems: (i) $\sum_{p \leq x} (\ln p)/p = \ln x + O(1)$, (ii) $\sum_{p \leq x} 1/p = \ln \ln x + M + O(1/\ln x)$ with $M = 0.2614972128\ldots$ the Meissel-Mertens constant, and (iii) $\prod_{p \leq x}(1 - 1/p) \sim e^{-\gamma}/\ln x$ with $\gamma$ Euler-Mascheroni.
Hadamard, J. — Sur la distribution des zéros de la fonction ζ(s) et ses conséquences arithmétiques · *Bulletin de la Société Mathématique de France* 24 (1896), 199-220. Proves the prime number theorem $\pi(x) \sim x/\ln x$ via complex-analytic estimates on $\zeta(s)$ along the line $\Re(s) = 1$, exploiting the non-vanishing of $\zeta(1 + it)$ for $t \neq 0$.
de la Vallée Poussin, C. — Recherches analytiques sur la théorie des nombres premiers · *Annales de la Société Scientifique de Bruxelles* 20 (1896), 183-256. Independently of Hadamard, proves the prime number theorem and quantifies the error term, giving $\pi(x) = \mathrm{Li}(x) + O(x \exp(-c\sqrt{\ln x}))$ for some $c > 0$.
Brun, V. — La série 1/5 + 1/7 + 1/11 + ... où les dénominateurs sont nombres premiers jumeaux est convergente ou finie · *Bulletin des Sciences Mathématiques* 43 (1919), 100-128. Introduces the Brun sieve and proves the convergence of the sum of reciprocals of twin primes, defining Brun's constant $B_2 = \sum_{p, p+2 \text{ prime}} (1/p + 1/(p+2)) \approx 1.902160583\ldots$.
Furstenberg, H. — On the infinitude of primes · *American Mathematical Monthly* 62 (1955), 353. A topological proof: equip $\mathbb{Z}$ with the topology generated by arithmetic progressions $\{a + n q : n \in \mathbb{Z}\}$; each progression is both open and closed; if there were finitely many primes, the complement of $\{-1, 1\}$ would be a finite union of closed sets, hence closed — contradicting that $\{-1, 1\}$ is not open.
Rivest, R., Shamir, A., & Adleman, L. — A method for obtaining digital signatures and public-key cryptosystems · *Communications of the ACM* 21 (1978), 120-126. The RSA cryptosystem: security relies on the computational hardness of factoring a product of two large primes — a direct application of the fundamental theorem of arithmetic combined with the asymmetry between multiplication and factorisation.
Zhang, Y. — Bounded gaps between primes · *Annals of Mathematics* 179 (2014), 1121-1174. Proves the existence of a finite constant $H$ (originally $H = 70{,}000{,}000$) such that infinitely many prime pairs $p < q$ satisfy $q - p \leq H$. The first unconditional bounded-gaps result.
Maynard, J. — Small gaps between primes · *Annals of Mathematics* 181 (2015), 383-413. Simplifies and strengthens Zhang's argument via a modified Selberg-sieve weight, reducing $H$ to $600$; the Polymath8b collaboration further reduced $H$ to $246$ in 2014.
Hardy, G. H. & Wright, E. M. — An Introduction to the Theory of Numbers · Oxford University Press, 6th edition (2008), revised by D. R. Heath-Brown and J. H. Silverman with a foreword by A. Wiles. Chapters I-II contain the divisibility and unique-factorisation theory; Chapter XXII contains the Chebyshev bounds, Mertens theorems, and the analytic prelude to the prime number theorem.
Apostol, T. M. — Introduction to Analytic Number Theory · Springer Undergraduate Texts in Mathematics (1976). Chapters 1-2 develop divisibility, the fundamental theorem, Mertens estimates, and the Chebyshev psi/theta functions in preparation for the analytic proof of the prime number theorem in Chapter 13.
Tenenbaum, G. — Introduction to Analytic and Probabilistic Number Theory · Cambridge University Press, 3rd edition (2015), §I. The modern systematic treatment of elementary techniques in analytic number theory: Abel summation, Mertens theorems with explicit error terms, the elementary Selberg-Erdős proof of the prime number theorem, and the analytic apparatus underlying the Riemann hypothesis.

Estimated time

beginner: 18m
intermediate: 40m
master: 85m