Dirichlet's theorem on arithmetic progressions

In number theory, Dirichlet's theorem, also called the Dirichlet prime number theorem, states that for any two positive coprime integers a and d, there are infinitely many primes of the form a + nd, where n is also a positive integer. In other words, there are infinitely many primes that are congruent to a modulo d. The numbers of the form a + nd form an arithmetic progression

${\displaystyle a,\ a+d,\ a+2d,\ a+3d,\ \dots ,\ }$

and Dirichlet's theorem states that this sequence contains infinitely many prime numbers. The theorem extends Euclid's theorem that there are infinitely many prime numbers (of the form 1 + 2n). Stronger forms of Dirichlet's theorem state that for any such arithmetic progression, the sum of the reciprocals of the prime numbers in the progression diverges and that different such arithmetic progressions with the same modulus have approximately the same proportions of primes. Equivalently, the primes are evenly distributed (asymptotically) among the congruence classes modulo d containing a's coprime to d.

The theorem is named after the German mathematician Peter Gustav Lejeune Dirichlet, who proved it in 1837.

The primes of the form 4n + 3 are (sequence A002145 in the OEIS)

3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83, 103, 107, 127, 131, 139, 151, 163, 167, 179, 191, 199, 211, 223, 227, 239, 251, 263, 271, 283, ...

They correspond to the following values of n: (sequence A095278 in the OEIS)

0, 1, 2, 4, 5, 7, 10, 11, 14, 16, 17, 19, 20, 25, 26, 31, 32, 34, 37, 40, 41, 44, 47, 49, 52, 55, 56, 59, 62, 65, 67, 70, 76, 77, 82, 86, 89, 91, 94, 95, ...

The strong form of Dirichlet's theorem implies that

${\displaystyle {\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{11}}+{\frac {1}{19}}+{\frac {1}{23}}+{\frac {1}{31}}+{\frac {1}{43}}+{\frac {1}{47}}+{\frac {1}{59}}+{\frac {1}{67}}+\cdots }$

is a divergent series.

Sequences dn + a with odd d are often ignored because half the numbers are even and the other half is the same numbers as a sequence with 2d, if we start with n = 0. For example, 6n + 1 produces the same primes as 3n + 1, while 6n + 5 produces the same as 3n + 2 except for the only even prime 2. The following table lists several arithmetic progressions with infinitely many primes and the first few ones in each of them.

We can generate some forms of primes by using an iterative method. For example, we can generate primes of the form ${\displaystyle 4n+3}$by using the following method:

Let ${\displaystyle a_{0}=4(1)+3=7}$. Then we let ${\displaystyle a_{1}=4a_{0}+3=4(7)+3=31}$which is prime. We continue by computing ${\displaystyle 4(7)(31)+3=871=13(67)}$. Because ${\displaystyle 4(7)(31)+3}$is of the form ${\displaystyle 4n+3}$, either 13 or 67 is of the form ${\displaystyle 4n+3}$. We have that ${\displaystyle 67=4(16)+3}$and is prime, so ${\displaystyle a_{3}=67}$. We then continue this process to find successive primes of the form ${\displaystyle 4n+3}$(Silverman 2013).

Since the primes thin out, on average, in accordance with the prime number theorem, the same must be true for the primes in arithmetic progressions. It is natural to ask about the way the primes are shared between the various arithmetic progressions for a given value of d (there are d of those, essentially, if we do not distinguish two progressions sharing almost all their terms). The answer is given in this form: the number of feasible progressions modulo d — those where a and d do not have a common factor > 1 — is given by Euler's totient function

${\displaystyle \varphi (d).\ }$

Further, the proportion of primes in each of those is

${\displaystyle {\frac {1}{\varphi (d)}}.\ }$

For example, if d is a prime number q, each of the q − 1 progressions

${\displaystyle q+1,2q+1,3q+1,\dots \ }$

${\displaystyle q+2,2q+2,3q+2,\dots \ }$

${\displaystyle \dots \ }$

${\displaystyle q+q-1,2q+q-1,3q+q-1,\dots \ }$

(all except ${\displaystyle q,2q,3q,\dots \ }$)

contains a proportion 1/(q − 1) of the primes.

When compared to each other, progressions with a quadratic nonresidue remainder have typically slightly more elements than those with a quadratic residue remainder (Chebyshev's bias).

In 1737, Euler related the study of prime numbers to what is known now as the Riemann zeta function: he showed that the value ${\displaystyle \zeta (1)}$reduces to a ratio of two infinite products, Π p / Π (p − 1), for all primes p, and that the ratio is infinite. In 1775, Euler stated the theorem for the cases of a + nd, where a = 1. This special case of Dirichlet's theorem can be proven using cyclotomic polynomials. The general form of the theorem was first conjectured by Legendre in his attempted unsuccessful proofs of quadratic reciprocity — as Gauss noted in his Disquisitiones Arithmeticae — but it was proved by Dirichlet (1837) with Dirichlet L-series. The proof is modeled on Euler's earlier work relating the Riemann zeta function to the distribution of primes. The theorem represents the beginning of rigorous analytic number theory.

Atle Selberg (1949) gave an elementary proof.

Dirichlet's theorem is proved by showing that the value of the Dirichlet L-function (of a non-trivial character) at 1 is nonzero. The proof of this statement requires some calculus and analytic number theory (Serre 1973). The particular case a = 1 (i.e., concerning the primes that are congruent to 1 modulo some n) can be proven by analyzing the splitting behavior of primes in cyclotomic extensions, without making use of calculus (Neukirch 1999, §VII.6).

Although the proof of Dirichlet's Theorem makes use of calculus and analytic number theory, some proofs of examples are much more straightforward. In particular, the proof of the example of infinitely many primes of the form ${\displaystyle 4n+3}$makes an argument similar to the one made in the proof of Euclid's theorem (Silverman 2013). The proof is given below:

We want to prove that there are infinitely many primes of the form ${\displaystyle 4n+3}$. Assume, for contradiction, that there are only finitely many primes of the form ${\displaystyle 4n+3}$. We then compile a list of all such primes ${\displaystyle 3,p_{1},p_{2},...,p_{m}}$where ${\displaystyle p_{1}<p_{2}<...<p_{m}}$. Let ${\displaystyle N=4p_{1}p_{2}...p_{m}+3}$. It is clear that none of the primes in the list ${\displaystyle 3,p_{1},p_{2},...,p_{m}}$divide ${\displaystyle N}$. Next, suppose that ${\displaystyle N}$is composite. Then ${\displaystyle N}$has unique prime factorization ${\displaystyle N=a_{1}a_{2}...a_{r}}$where each ${\displaystyle a_{i}}$is prime. Because ${\displaystyle N\equiv 3{\bmod {4}}}$, ${\displaystyle N}$is odd and must be the product of only odd primes. Any odd prime ${\displaystyle p}$must be such that ${\displaystyle p\equiv 1{\bmod {4}}}$or ${\displaystyle p\equiv 3{\bmod {4}}}$. It cannot be that ${\displaystyle a_{i}\equiv 1{\bmod {4}}}$${\displaystyle \forall a_{i}}$because if this were the case, then ${\displaystyle N\equiv 1{\bmod {4}}}$. So there exists a prime ${\displaystyle a_{i}\equiv 3{\bmod {4}}}$such that ${\displaystyle a_{i}\mid N}$. However, none of the primes in the list ${\displaystyle 3,p_{1},p_{2},...,p_{m}}$divide ${\displaystyle N}$, a contradiction. Therefore ${\displaystyle N}$must be prime and ${\displaystyle N>p_{m}}$. Hence, ${\displaystyle N}$is a prime of the form ${\displaystyle 4n+3}$, but it isn't included in the list ${\displaystyle 3,p_{1},p_{2},...,p_{m}}$. Thus, the list doesn't contain all such primes and there must be infinitely many primes of the form ${\displaystyle 4n+3}$(Silverman 2013).

The Bunyakovsky conjecture generalizes Dirichlet's theorem to higher-degree polynomials. Whether or not even simple quadratic polynomials such as x² + 1 (known from Landau's fourth problem) attain infinitely many prime values is an important open problem.

Dickson's conjecture generalizes Dirichlet's theorem to more than one polynomial.

Schinzel's hypothesis H generalizes these two conjectures, i.e. generalizes to more than one polynomial with degree larger than one.

In algebraic number theory, Dirichlet's theorem generalizes to the Chebotarev's density theorem.

Linnik's theorem (1944) concerns the size of the smallest prime in a given arithmetic progression. Linnik proved that the progression a + nd (as n ranges through the positive integers) contains a prime of magnitude at most cd^L for absolute constants c and L. Subsequent researchers have reduced L to 5.

An analogue of Dirichlet's theorem holds in the framework of dynamical systems (T. Sunada and A. Katsuda, 1990).

Shiu showed that any arithmetic progression satisfying the hypothesis of Dirichlet's theorem will in fact contain arbitrarily long runs of consecutive prime numbers.

• Bombieri–Vinogradov theorem
• Brun–Titchmarsh theorem
• Siegel–Walfisz theorem
• Dirichlet's approximation theorem
• Green–Tao theorem

• Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR 0434929, Zbl 0335.10001
• Weisstein, Eric W. "Dirichlet's Theorem". MathWorld.
• Chris Caldwell, "Dirichlet's Theorem on Primes in Arithmetic Progressions" at the Prime Pages.
• Dirichlet, P. G. L. (1837), "Beweis des Satzes, dass jede unbegrenzte arithmetische Progression, deren erstes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Factor sind, unendlich viele Primzahlen enthält" [Proof of the theorem that every unbounded arithmetic progression, whose first term and common difference are integers without common factors, contains infinitely many prime numbers], Abhandlungen der Königlichen Preußischen Akademie der Wissenschaften zu Berlin, 48: 45–71
• Neukirch, Jürgen (1999), Algebraic number theory. Translated from the 1992 German original and with a note by Norbert Schappacher, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 322, Berlin: Springer-Verlag, ISBN 3-540-65399-6, MR 1697859, Zbl 0956.11021.
• Selberg, Atle (1949), "An elementary proof of Dirichlet's theorem about primes in an arithmetic progression", Annals of Mathematics, 50 (2): 297–304, doi:10.2307/1969454, JSTOR 1969454, Zbl 0036.30603.
• Serre, Jean-Pierre (1973), A course in arithmetic, Graduate Texts in Mathematics, vol. 7, New York; Heidelberg; Berlin: Springer-Verlag, ISBN 3-540-90040-3, Zbl 0256.12001.
• Sunada, Toshikazu; Katsuda, Atsushi (1990), "Closed orbits in homology classes", Publ. Math. IHÉS, 71: 5–32, doi:10.1007/BF02699875, S2CID 26251216.
• Silverman JH (2013) A Friendly Introduction to Number Theory: Pearson New International Edition, Pearson Education.

• Scans of the original paper in German
• Dirichlet: There are infinitely many prime numbers in all arithmetic progressions with first term and difference coprime English translation of the original paper at the arXiv
• Dirichlet's Theorem by Jay Warendorff, Wolfram Demonstrations Project.