Primes in Arithmetic Progressions
Euclid's trick proves that infinitely many primes end in 1 or 9 but cannot reach the primes ending in 3 or 7. Dirichlet's theorem of 1837 reaches every admissible progression, and this unit proves it in full: the characters of the residues modulo q and their orthogonality, the L-functions with their Euler products, and the key fact that no L-function vanishes at s = 1. The closing sections look at how evenly the primes are shared among the residue classes, at Chebyshev's bias, at Dirichlet's class number formula, and at the Green-Tao theorem on arithmetic progressions made of primes.
Unit 3 proved with Euclid’s trick that there are infinitely many primes of the form \(4k + 3\), and Unit 10 found a different trick for the primes \(4k + 1\). Nobody has ever found a trick of this kind for the primes that end in the digit \(7\), and Section 1 explains why none exists. What exists instead is the theorem that Peter Gustav Lejeune Dirichlet (1805-1859) proved in 1837: every arithmetic progression \(a, a + q, a + 2q, \ldots\) with \(\gcd(a, q) = 1\) contains infinitely many primes. Its proof was the first to use analysis, meaning infinite series and limits, to prove a statement about whole numbers that no other method had been able to reach, and its two tools, the characters and the \(L\)-functions, are now standard equipment of number theory. This unit builds them from the primitive roots of Unit 9 and the complex series of Unit 13, carries the proof through to the end, and then asks how evenly the primes are shared among the residue classes and whether the primes themselves can form long arithmetic progressions.
1 Euclid’s method and its limits
An arithmetic progression with first term \(a\) and common difference \(q \ge 1\) is the sequence \(a, a + q, a + 2q, \ldots\), and its terms are exactly the positive integers \(n\) with \(n \equiv a \pmod q\). If \(\gcd(a, q) = d > 1\), then \(d\) divides every term, so the progression contains at most one prime, namely \(d\) itself if \(d\) happens to be prime. The interesting case is therefore \(\gcd(a, q) = 1\), and the question is whether the progression then contains infinitely many primes. For \(q = 10\) the question is a question about last digits, because the residue of \(n\) modulo \(10\) is its last digit. From \(11\) on, every prime ends in \(1\), \(3\), \(7\), or \(9\), and among the \(168\) primes below \(1000\) these four last digits occur \(40\), \(42\), \(46\), and \(38\) times, about equally often.
For two of the four last digits, Euclid’s method works. Unit 3 showed that \(N = 4 p_1 p_2 \cdots p_r - 1\), built from any finite list of primes \(p_i \equiv 3 \pmod 4\), must have a prime factor \(\equiv 3 \pmod 4\) that is not on the list, because a product of primes \(\equiv 1 \pmod 4\) is itself \(\equiv 1 \pmod 4\). Unit 10 handled the primes \(\equiv 1 \pmod 4\) with the number \((n!)^{2} + 1\), whose odd prime factors are all \(\equiv 1 \pmod 4\) by the first supplement to the reciprocity law, which says that \(-1\) is a square modulo an odd prime \(p\) exactly when \(p \equiv 1 \pmod 4\). Both arguments share one design, a polynomial whose values have prime factors only in the wanted residue class and in the residue class of \(1\). Which primes can divide the values of a polynomial is governed by reciprocity laws, and this is where the limit of the method lies. Issai Schur (1875-1941) showed in 1912 that an argument of this shape exists whenever \(a^{2} \equiv 1 \pmod q\), and M. Ram Murty of Queen’s University proved in 1988 that it exists only then. For the primes ending in \(7\) this rules out any argument of Euclid’s kind, because \(7^{2} = 49 \equiv 9 \pmod{10}\), and the same holds for \(3\), since \(3^{2} \equiv 9\). No polynomial of Euclid’s kind can single out the primes ending in \(7\), and no variation of Euclid’s argument can prove that there are infinitely many of them. What can is the theorem of this unit.
The second sentence is what the proof delivers, and it says more than the first: a set of primes whose reciprocals have a divergent sum cannot be sparse. Unit 8 proved the same divergence for all primes by Euler’s method and Unit 12 measured its rate, and Dirichlet’s proof is Euler’s method with one new ingredient, namely a way to pick out a single residue class from the sum over all primes. That ingredient is the subject of the next section.