Dirichlet's theorem on arithmetic progressions

related topics
{math, number, function}
{rate, high, increase}

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.

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

They correspond to the following values of n:

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.

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.

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 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.

Full article ▸

related documents
Most significant bit
Infinite set
EXPTIME
Canonical LR parser
Condition number
Matrix addition
Linear span
Exponential time
Unification
Linear prediction
Rational root theorem
Constant term
Catalan's conjecture
Entire function
Symmetric tensor
Sather
Equation
Sum rule in integration
Interpreted language
Single precision
Commutative diagram
Hyperplane
Euler number
Atlas (topology)
Noetherian ring
BQP
Genus (mathematics)
Field of fractions
Cauchy's integral theorem
NC (complexity)