Added to Favorites

Related Searches

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, or in other words: there are infinitely many primes which are congruent to a modulo d. Moreover, the sum of the reciprocals of such primes diverges.## Examples

We get primes of the type 4n + 3 'only' for n with the values

## Distribution

Since the primes thin out, on average, 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## History

## See also

## References

## External links

This theorem extends Euclid's theorem that there are infinitely many primes (in this case of the form 3 + 4n, which are also the Gaussian primes, or of the form 1 + 2n, for every odd number, excluding 1). Note that the theorem does not say that there are infinitely many consecutive terms in the arithmetic progression

- a, a+d, a+2d, a+3d, ...,

which are prime.

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

Arithmetic progression | First 10 of infinitely many primes | OEIS id |
---|---|---|

2n + 1 | 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, … | |

4n + 1 | 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, … | |

4n + 3 | 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, … | |

6n + 1 | 7, 13, 19, 31, 37, 43, 61, 67, 73, 79, … | |

6n + 5 | 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, … | |

8n + 1 | 17, 41, 73, 89, 97, 113, 137, 193, 233, 241, … | |

8n + 3 | 3, 11, 19, 43, 59, 67, 83, 107, 131, 139, … | |

8n + 5 | 5, 13, 29, 37, 53, 61, 101, 109, 149, 157, … | |

8n + 7 | 7, 23, 31, 47, 71, 79, 103, 127, 151, 167, … | |

10n + 1 | 11, 31, 41, 61, 71, 101, 131, 151, 181, 191, … | |

10n + 3 | 3, 13, 23, 43, 53, 73, 83, 103, 113, 163, … | |

10n + 7 | 7, 17, 37, 47, 67, 97, 107, 127, 137, 157, … | |

10n + 9 | 19, 29, 59, 79, 89, 109, 139, 149, 179, 199, … |

- φ(d).

Further, the proportion of primes in each of those is

- 1/φ(d).

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

- q, 2q, 3q, ...

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

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 Gauss and proved by Dirichlet in 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.

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

- Linnik's theorem (1944)
- Bombieri–Vinogradov theorem
- Brun-Titchmarsh theorem
- Green–Tao theorem - there are arbitrarily long arithmetic progressions in the primes.
- Siegel-Walfisz theorem

- Chris Caldwell, "Dirichlet's Theorem on Primes in Arithmetic Progressions" at the Prime Pages.

- 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, The Wolfram Demonstrations Project.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday August 12, 2008 at 06:04:32 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday August 12, 2008 at 06:04:32 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.