 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 ≥ 0. In other words, there are infinitely many primes which are congruent to a modulo d. The numbers of the form a + nd form an arithmetic progression
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. Stronger forms of Dirichlet's theorem state that, for any arithmetic progression, the sum of the reciprocals of the prime numbers in the progression diverges, and that different arithmetic progressions with the same modulus have approximately the same proportions of primes. Equivalently, the primes are evenly distributed (asymptotically) among each congruence class modulo d.
Note that Dirichlet's theorem does not require the prime numbers in an arithmetic sequence to be consecutive. It is also known that there exist arbitrarily long finite arithmetic progressions consisting only of primes, but this is a different result, known as the Green–Tao theorem.
Contents
Examples
An integer is a prime for the Gaussian integers if it is a prime number (in the normal sense) that is congruent to 3 modulo 4. The primes of the type 4n + 3 are
 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, ….
They correspond to the following values of n:
 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
is a divergent series.
The following table lists several arithmetic progressions and the first few prime numbers in each of them.
Arithmetic
progressionFirst 10 of infinitely many primes OEIS id 2n + 1 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, … A065091 4n + 1 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, … A002144 4n + 3 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, … A002145 6n + 1 7, 13, 19, 31, 37, 43, 61, 67, 73, 79, … A002476 6n + 5 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, … A007528 8n + 1 17, 41, 73, 89, 97, 113, 137, 193, 233, 241, … A007519 8n + 3 3, 11, 19, 43, 59, 67, 83, 107, 131, 139, … A007520 8n + 5 5, 13, 29, 37, 53, 61, 101, 109, 149, 157, … A007521 8n + 7 7, 23, 31, 47, 71, 79, 103, 127, 151, 167, … A007522 10n + 1 11, 31, 41, 61, 71, 101, 131, 151, 181, 191, … A030430 10n + 3 3, 13, 23, 43, 53, 73, 83, 103, 113, 163, … A030431 10n + 7 7, 17, 37, 47, 67, 97, 107, 127, 137, 157, … A030432 10n + 9 19, 29, 59, 79, 89, 109, 139, 149, 179, 199, … A030433 Distribution
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. One naturally then asks 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 don't 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
Further, the proportion of primes in each of those is
For example if d is a prime number q, each of the q − 1 progressions, other than
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).
History
Euler stated that every arithmetic progression beginning with 1 contains an infinite number of primes. The theorem in the above form was first conjectured by Legendre in his attempted unsuccessful proofs of quadratic reciprocity and proved by Dirichlet in (Dirichlet 1837) with Dirichlet Lseries. 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.
Generalizations
The Bunyakovsky conjecture generalizes Dirichlet's theorem to higherorder polynomials. Whether or not even simple quadratic polynomials such as x^{2} + 1 attain infinitely many prime values is an important open problem.
In algebraic number theory, Dirichlet's theorem generalizes to Chebotarev's density theorem.
See also
 Linnik's theorem (1944)
 Bombieri–Vinogradov theorem
 Brun–Titchmarsh theorem
 Siegel–Walfisz theorem
 Dirichlet's approximation theorem
References
 Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New YorkHeidelberg: SpringerVerlag, ISBN 9780387901633, MR0434929
 Weisstein, Eric W., "Dirichlet's Theorem" from 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", Abhand. Ak. Wiss. Berlin 48
 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.
External links
 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.
Categories: Prime numbers
 Zeta and Lfunctions
 Theorems in number theory
Wikimedia Foundation. 2010.
Look at other dictionaries:
Dirichlet's theorem — may refer to any of several mathematical theorems due to Johann Peter Gustav Lejeune Dirichlet. Dirichlet s theorem on arithmetic progressions Dirichlet s approximation theorem Dirichlet s unit theorem Dirichlet conditions Dirichlet boundary… … Wikipedia
Problems involving arithmetic progressions — are of interest in number theory,cite journalauthor=Samuel S. Wagstaff, Jr.authorlink= url= title=Some Questions About Arithmetic Progressions journal=The American Mathematical Monthly volume=86issue=7pages=579–582year=1979… … Wikipedia
Dirichlet density — This article is not about the Dirichlet distribution of probability theory. In mathematics, the Dirichlet density (or analytic density) of a set of primes, named after Johann Gustav Dirichlet, is a measure of the size of the set that is easier to … Wikipedia
Dirichlet character — In number theory, Dirichlet characters are certain arithmetic functions which arise from completely multiplicative characters on the units of . Dirichlet characters are used to define Dirichlet L functions, which are meromorphic functions with a… … Wikipedia
Dirichlet's approximation theorem — In number theory, Dirichlet s theorem on Diophantine approximation, also called Dirichlet s approximation theorem, states that for any real number α and any positive integer N, there exists integers p and q such that 1 ≤ q ≤ N and This is a… … Wikipedia
Dirichlet Lfunction — In mathematics, a Dirichlet L series is a function of the form Here χ is a Dirichlet character and s a complex variable with real part greater than 1. By analytic continuation, this function can be extended to a meromorphic function on the whole… … Wikipedia
Johann Peter Gustav Lejeune Dirichlet — Gustav Lejeune Dirichlet Johann Peter Gustav Lejeune Dirichlet Born 13 Fe … Wikipedia
Green–Tao theorem — In mathematics, the Green–Tao theorem, proved by Ben Green and Terence Tao in 2004, [Ben Green and Terence Tao, [http://arxiv.org/abs/math.NT/0404188 The primes contain arbitrarily long arithmetic progressions] ,8 Apr 2004.] states that the… … Wikipedia
Chebotarev's density theorem — in algebraic number theory describes statistically the splitting of primes in a given Galois extension K of the field Q of rational numbers. Generally speaking, a prime integer will factor into several ideal primes in the ring of algebraic… … Wikipedia
Primes in arithmetic progression — In number theory, the phrase primes in arithmetic progression refers to at least three prime numbers that are consecutive terms in an arithmetic progression, for example the primes (3, 7, 11) (it does not matter that 5 is also prime). There are… … Wikipedia