Dirichlet's Theorem on Primes in Arithmetic Progressions

The precise statement

Let q ≥ 1 be an integer (the modulus) and let a be an integer with gcd(a, q) = 1. Then there are infinitely many primes p satisfying p ≡ a (mod q); equivalently, the arithmetic progression

• a, a + q, a + 2q, a + 3q, …

contains infinitely many prime numbers.

The coprimality hypothesis is not a technicality — it is exactly the right condition. If gcd(a, q) = d > 1, then every term a + nq is divisible by d, so the progression can contain at most the single prime d (and only if a = d). So Dirichlet's theorem says: whenever the progression is not obstructed by a common factor, it is as rich in primes as it possibly could be.

Dirichlet actually proved something sharper, the strong form: the sum ∑ 1/p taken over primes p ≡ a (mod q) diverges. This not only forces infinitely many such primes but says they are 'as dense' (in the reciprocal-sum sense) as the full set of primes.

The picture: sorting primes into residue classes

Fix a modulus q. Every integer coprime to q lands in one of the φ(q) invertible residue classes mod q, where φ is Euler's totient. For q = 10 the four coprime classes are 1, 3, 7, 9 — primes end (in base 10) in 1, 3, 7, or 9.

The naïve question is: do the primes distribute themselves among these φ(q) classes, or could they secretly avoid one? Dirichlet's theorem says none of the allowed classes is starved — each gets infinitely many primes. The Prime Number Theorem for arithmetic progressions later made this quantitative: the primes split with perfect asymptotic fairness, each coprime class receiving a fraction 1/φ(q) of them.

The mental image is a comb with φ(q) teeth (the coprime classes). Euclid tells you the whole comb catches infinitely many primes. Dirichlet tells you every single tooth does. The subtlety is that primes are defined multiplicatively while residue classes are defined additively — bridging the two is precisely what makes the theorem hard.

The key idea: characters detect residue classes

The mechanism is a Fourier analysis on the group (ℤ/qℤ)* of units mod q. A Dirichlet character mod q is a homomorphism χ: (ℤ/qℤ)* → ℂ*, extended to be 0 on integers sharing a factor with q. There are exactly φ(q) of them, and their orthogonality relations let you isolate a single residue class: for gcd(a, q) = 1,

• (1/φ(q)) ∑_χ χ̄(a) χ(n) = 1 if n ≡ a (mod q), else 0.

Attach to each χ its Dirichlet L-function L(s, χ) = ∑_n≥1 χ(n)/nˢ = ∏_p (1 − χ(p)/pˢ)⁻¹. Taking logarithms, ∑_p χ(p)/pˢ ≈ log L(s, χ). Combining with the orthogonality relation, the sum ∑ 1/pˢ over p ≡ a (mod q) equals (1/φ(q)) ∑_χ χ̄(a) log L(s, χ).

As s → 1⁺ the principal character χ₀ contributes log L(s, χ₀) → +∞ (it's essentially the Riemann zeta pole). The whole theorem reduces to one delicate fact: for every non-principal character χ ≠ χ₀, the value L(1, χ) ≠ 0. Then those terms stay finite, the χ₀ term dominates, and the sum diverges — infinitely many primes.

Worked example: primes ≡ 1 and 3 (mod 4)

Take q = 4. The units are {1, 3}, so φ(4) = 2 and there are two characters. The principal character χ₀ sends 1 ↦ 1, 3 ↦ 1 (and even numbers ↦ 0). The non-principal character χ is the sign character:

• χ(n) = 1 if n ≡ 1 (mod 4), χ(n) = −1 if n ≡ 3 (mod 4), χ(n) = 0 if n is even.

Its L-function is L(s, χ) = 1 − 3⁻ˢ + 5⁻ˢ − 7⁻ˢ + 9⁻ˢ − ⋯. At s = 1 this is the Leibniz series 1 − 1/3 + 1/5 − 1/7 + ⋯ = π/4 ≠ 0. That single nonzero value is the crux: it certifies L(1, χ) ≠ 0, so both classes receive infinitely many primes.

Concretely, primes ≡ 1 (mod 4): 5, 13, 17, 29, 37, … and primes ≡ 3 (mod 4): 3, 7, 11, 19, 23, … — both lists never end. Here the non-vanishing is elementary (π/4 is visibly positive); for a general modulus q it requires real work, which is what Dirichlet supplied.

Why the hypotheses matter, and what's really hard

Drop coprimality and it fails instantly. The progression 2, 6, 10, 14, … (a = 2, q = 4, gcd = 2) contains only one prime, 2; every later term is even. With gcd(a, q) = d > 1, every term is a multiple of d, so at most one prime survives. Coprimality is necessary and sufficient for the conclusion.

The genuinely hard step is L(1, χ) ≠ 0 for χ ≠ χ₀. If some L(1, χ) vanished, its zero would cancel the pole and the divergence could collapse, potentially leaving a residue class prime-free. For complex characters this non-vanishing follows from a slick counting argument; the delicate case is a real non-principal character, where Dirichlet's proof connects L(1, χ) to a class number of a quadratic form, forcing it to be strictly positive (his class number formula).

This is the point of contact with the Riemann zeta function and the Generalized Riemann Hypothesis: GRH asserts all nontrivial zeros of every L(s, χ) lie on Re(s) = 1/2, which would give the sharpest possible error terms for how evenly primes spread across residue classes.

Applications and significance

Dirichlet's 1837 paper invented analytic number theory. The template — encode an arithmetic question in a Dirichlet series, study its analytic behavior near s = 1, and read off arithmetic from analysis — became the field's central engine, leading directly to:

• the Prime Number Theorem (Hadamard and de la Vallée Poussin, 1896), whose proof mirrors Dirichlet's via non-vanishing on the line Re(s) = 1;
• the Prime Number Theorem for arithmetic progressions: π(x; q, a) ~ (1/φ(q)) · x/ln x, making 'infinitely many' quantitative;
• modern sieve theory, the Bombieri–Vinogradov theorem (an averaged GRH), and additive results like Green–Tao (arbitrarily long prime progressions).

Practically, it underpins heuristics used throughout number theory and cryptography — for instance the expectation that primes of a prescribed form (fed into RSA-style constructions) are plentiful. Conceptually, it is the prototype for the philosophy that L-functions govern the distribution of primes, a thread running through the Langlands program and the Riemann Hypothesis itself.

Dirichlet's theorem compared with related results on primes

Result	Hypothesis	Conclusion	Method
Euclid (c. 300 BC)	None (q = 1)	Infinitely many primes	Elementary contradiction
Dirichlet (1837)	gcd(a, q) = 1	Infinitely many primes ≡ a (mod q)	Characters + L-functions
Dirichlet, strong form	gcd(a, q) = 1	∑ 1/p over p ≡ a (mod q) diverges	log L(1, χ) analysis
Prime Number Theorem for APs (de la Vallée Poussin, 1896)	gcd(a, q) = 1	π(x; q, a) ~ (1/φ(q))·x/ln x	Zero-free region of L(s, χ)
Green–Tao (2004)	None on a, q	Arbitrarily long APs consisting of primes	Additive combinatorics