Primes in Arithmetic Progressions: Statement

The character/$L$-function technique introduced for this theorem is the direct ancestor of the entire modern apparatus of $L$-functions: Dedekind zeta functions of number fields, Artin $L$-functions attached to Galois representations, automorphic $L$-functions in the Langlands program, and elliptic curve $L$-functions in the Birch–Swinnerton-Dyer conjecture all generalize the pattern "attach an $L$-function to an algebraic/arithmetic object, study analytic properties at the edge of convergence, extract arithmetic information." In cryptography, the density of primes in residue classes underlies heuristics for prime generation algorithms (e.g., searching for primes of a specific bit-length and specific residue properties for RSA or elliptic-curve parameter selection), and the equidistribution result assures that restricting search to certain classes for efficiency reasons does not create scarcity. In computational number theory, Dirichlet's theorem justifies sieve-based primality search strategies restricted to classes coprime to small moduli (wheel factorization). In probability and statistics, the equidistribution $1/\phi(q)$ is a paradigm case of an asymptotic "law" extracted from a deterministic but seemingly erratic sequence, analogous in spirit to equidistribution results in ergodic theory and to Weyl's equidistribution theorem for irrational rotations. In physics, the analytic continuation and pole-detection method (finding arithmetic information encoded in poles/zeros of a Dirichlet series) parallels the use of partition functions and their singularities in statistical mechanics.

Ask the tutor: How does the nonvanishing $L(1,\chi) \neq 0$ get proved for a general Dirichlet character, and how does it connect to class numbers of quadratic fields?

Think of the integers laid along a number line and colored by residue mod $q$. Fixing $q=4$, the primes larger than $2$ must be odd, so they fall into the class $1 \bmod 4$ or the class $3 \bmod 4$ — never $0$ or $2 \bmod 4$, since those are even. The question "are there infinitely many primes $\equiv 3 \pmod 4$" is answered by a short, classical Euclid-style trick (shown below). But "are there infinitely many primes $\equiv 1 \pmod 4$" already resists elementary tricks in general moduli, and for a general modulus $q$ and general admissible residue $a$, no purely elementary argument is known that handles all cases simultaneously — this is exactly why Dirichlet reached for complex analysis. The mechanism is a Fourier-analytic idea transplanted to number theory. The indicator function of a single residue class mod $q$ is, by the orthogonality relations, an average of characters $\chi(n)$ — the characters are the "harmonics" on the finite abelian group $(\mathbb{Z}/q\mathbb{Z})^\times$. Summing $\log p$ over primes in a fixed class becomes a linear combination of sums $\sum_p \chi(p)\log p / p^s$ over all characters $\chi$ mod $q$, weighted by $\overline{\chi(a)}$. Each such character sum is controlled by the corresponding $L$-function via $-L'(s,\chi)/L(s,\chi) = \sum_n \Lambda(n)\chi(n) n^{-s}$. The trivial character's $L$-function is $\zeta(s)$ in disguise, which has a genuine pole at $s=1$ — this pole is the source of the primes, exactly as in the ordinary Prime Number Theorem. Every other character's $L$-function must, crucially, be nonzero at $s=1$; otherwise its logarithmic derivative would itself have a pole there, contributing spurious poles that could cancel the one real pole coming from $\chi_0$, and the argument would give no primes at all in the class.

Both statements require $\gcd(a,q)=1$: this is not a simplifying convenience but a genuine necessary condition, verified next.

This is why Dirichlet's theorem is stated only for $\gcd(a,q)=1$: it is exactly the boundary case where the elementary divisibility obstruction from the lemma disappears, and the number of admissible classes is precisely $\phi(q)$, explaining why $\phi(q)$ appears as the equidistribution denominator. We now prove the qualitative theorem completely for $q = 4$, which contains, in miniature, every structural ingredient of the general proof (character orthogonality, an $L$-function for each character, the pole of $\zeta$ at $\chi_0$, and nonvanishing of $L(1,\chi)$ for $\chi \neq \chi_0$), while remaining fully elementary and self-contained — no properties of $L(1,\chi)$ beyond what we prove by hand are used.

The proof technique used above — analytic continuation of an Euler product's logarithmic derivative, combined with the nonvanishing of $L(1,\chi)$ to isolate a divergent contribution — is exactly the technique in the general proof of Dirichlet's theorem. In general modulus $q$, one runs the identical argument with all $\phi(q)$ characters mod $q$ simultaneously:

and the same dichotomy occurs: the principal character $\chi_0$ contributes the divergent $\zeta$-pole term $\frac{1}{\phi(q)}\cdot\frac{1}{s-1} + O(1)$, while every nonprincipal $\chi$ contributes a bounded term provided $L(1,\chi) \neq 0$. The nonvanishing $L(1,\chi) \neq 0$ for a general nonprincipal character mod $q$ (real or complex-valued) is the one deep analytic fact not proved here in general; it is a substantial theorem in its own right (via class number formulas for real characters, and a positivity trick of Mertens/de la Vallée Poussin type combining $\zeta(s)$ and all $L(s,\chi)$ for complex characters), properly the subject of a dedicated treatment of Dirichlet $L$-functions and is treated as the key external input for the general theorem here.

Example 1: modulus 5, exhibiting all four Dirichlet characters and orthogonality by hand. Let $q = 5$. Then $(\mathbb{Z}/5\mathbb{Z})^\times = \{1,2,3,4\}$ is cyclic of order $4$, generated by $g=2$ ($2^1=2, 2^2=4, 2^3=3, 2^4=1$). The four characters $\chi_j$, $j=0,1,2,3$, are determined by $\chi_j(2) = i^j$ where $i = \sqrt{-1}$:

(Here $\chi_2$ is the unique real nonprincipal character, the Legendre-symbol character mod 5; $\chi_1,\chi_3$ are complex conjugates of each other.) Let us verify orthogonality isolates $n \equiv 2 \pmod 5$ correctly:

At $n=2$: $\overline{\chi_0(2)}\chi_0(2) + \overline{\chi_1(2)}\chi_1(2) + \overline{\chi_2(2)}\chi_2(2)+\overline{\chi_3(2)}\chi_3(2) = 1\cdot1 + \bar i \cdot i + (-1)(-1) + \overline{(-i)}\cdot(-i) = 1 + 1 + 1 + 1 = 4$, giving $\frac14 \cdot 4 = 1$. ✓. At $n=3$: $\overline{\chi_0(2)}\chi_0(3) + \overline{\chi_1(2)}\chi_1(3) + \overline{\chi_2(2)}\chi_2(3) + \overline{\chi_3(2)}\chi_3(3) = 1\cdot 1 + \bar i(-i) + (-1)(-1) + \overline{(-i)}(i) = 1 + (-i)(-i) + 1 + i(i)$. Let us be careful: $\bar i = -i$, so $\overline{\chi_1(2)}\chi_1(3) = (-i)(-i) = i^2 = -1$. And $\overline{\chi_3(2)} = \overline{-i} = i$, so $\overline{\chi_3(2)}\chi_3(3) = i \cdot i = i^2 = -1$. Total: $1 + (-1) + 1 + (-1) = 0$, giving $\frac14 \cdot 0 = 0$. ✓ matches $[3 \equiv 2 \pmod 5] = 0$. This confirms concretely, in a modulus with genuinely complex characters (unlike the $q=4$ case, which only involved real values $\pm1$), that the orthogonality relation used in the proof correctly isolates a single class. Extending Step 2 of the $q=4$ proof to $q=5$ would require establishing $L(1,\chi_j) \neq 0$ for $j=1,2,3$ — routine for $\chi_2$ (real character; class-number-type positivity) but requiring the general complex-character nonvanishing argument for $\chi_1,\chi_3$.

Example 2: numerically checking equidistribution, $q=10$, up to $x = 200$. The admissible residues mod $10$ are $a \in \{1,3,7,9\}$ (coprime to $10$), so $\phi(10)=4$ and Dirichlet's theorem predicts each class holds asymptotically $1/4$ of all primes $>5$. Primes up to $200$ (excluding $2,5$, the non-admissible small primes): there are $46$ primes below $200$ total, minus the two exceptions $2,5$, leaving $44$ primes distributed among the four classes. Direct counting gives:

• $p \equiv 1 \pmod{10}$: $11, 31, 41, 61, 71, 101, 131, 151, 181, 191$ — count $10$.
• $p \equiv 3 \pmod{10}$: $3, 13, 23, 43, 53, 73, 83, 103, 113, 163, 173, 193$ — count $12$.
• $p \equiv 7 \pmod{10}$: $7, 17, 37, 47, 67, 97, 107, 127, 137, 157, 167, 197$ — count $12$.
• $p \equiv 9 \pmod{10}$: $19, 29, 59, 79, 89, 109, 139, 149, 179, 199$ — count $10$.

Total $10+12+12+10 = 44$. ✓ matches the total count. Each class has roughly $44/4 = 11$ primes; the actual counts $10,12,12,10$ are close, illustrating equidistribution as a limiting statement — at this small range $x=200$ the fluctuation is still visible (this is the beginning of the phenomenon called Chebyshev's bias, where classes containing quadratic non-residues mod $q$ tend to lead slightly more often at small $x$, a second-order effect entirely consistent with, and not contradicting, the first-order asymptotic $\pi(x;10,a) \sim \frac14 \pi(x)$ that Dirichlet's quantitative theorem guarantees only in the limit).