Engineering / Mathematics — The Distribution of Primes
Primes in Arithmetic Progressions
Dirichlet's theorem on primes in arithmetic progressions, equidistribution across residue classes, and computational consequences.
Executive summary
Dirichlet proved that any arithmetic progression whose first term and common difference are coprime contains infinitely many primes. The proof introduced L-functions and effectively founded analytic number theory.
The stronger statement is equidistribution: the primes are shared equally among the admissible residue classes, which is what justifies generating primes with prescribed congruence conditions.
Learning objectives
- State Dirichlet's theorem and the coprimality condition.
- State the equidistribution refinement.
- Apply the result to constrained prime generation.
01The theorem
Dirichlet's theorem
If gcd(a, n) = 1, the arithmetic progression a, a+n, a+2n, ... contains infinitely many primes.
The coprimality condition is clearly necessary: if a prime p divides both a and n, then every term is divisible by p and at most one term can be prime.
What is not obvious is sufficiency. Elementary proofs exist for particular progressions — the primes congruent to 3 modulo 4 yield to a Euclid-style argument — but no elementary proof covers the general case.
02Equidistribution
Prime number theorem for arithmetic progressions
For gcd(a, n) = 1, the number of primes up to x congruent to a modulo n is
π(x; n, a) ~ π(x) / φ(n).
So the primes distribute themselves evenly among the φ(n) admissible residue classes. No class is favoured asymptotically, though bias at finite ranges is a real and studied phenomenon.
| Modulus n | Admissible classes | Share of primes each |
|---|---|---|
| 4 | 1, 3 | 1/2 |
| 6 | 1, 5 | 1/2 |
| 10 | 1, 3, 7, 9 | 1/4 |
| general n | φ(n) classes | 1/φ(n) |
03Constrained prime generation
Cryptographic applications frequently require primes satisfying congruence conditions — a prime p with p ≡ 3 (mod 4) for simple square-root extraction, or with q | p−1 for a subgroup of prescribed order.
p ≡ 3 (mod 4)
Square roots modulo p are computed as a single exponentiation, avoiding the Tonelli-style search. Half of all primes qualify.
q | p − 1 for a chosen prime q
Guarantees a subgroup of order q for discrete-log protocols. Generated by searching p = kq + 1 over k.
Safe primes: p = 2q + 1 with q prime
Makes the group structure maximally simple and resists small-subgroup attacks. Rarer, so generation is slower.
Equidistribution is what makes these searches predictable. Restricting to one residue class modulo n multiplies the expected number of trials by φ(n) relative to unrestricted search, and no worse — the density within an admissible class is uniform.
04Frequently asked questions
Is there a bias towards particular residue classes?
At finite ranges, yes. Chebyshev observed that primes congruent to 3 modulo 4 tend to lead those congruent to 1, and the phenomenon is now well understood as a bias that persists over long ranges while vanishing asymptotically.
Does the theorem give an effective bound on the least prime in a progression?
Linnik's theorem does, showing the least prime is bounded by n^L for an absolute constant L. Explicit values of L are large; under the generalised Riemann hypothesis much sharper bounds hold.
Why do safe primes lack a proved density?
Because their existence in abundance requires two conditions to hold simultaneously, and no method is known to prove infinitude of such pairs — the same obstacle that leaves the twin prime conjecture open.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 91-93.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.