In
number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
, Dirichlet's theorem, also called the Dirichlet
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a Product (mathematics), product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime ...
theorem, states that for any two positive
coprime
In number theory, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equiv ...
integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
s ''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
In computing and mathematics, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another, the latter being called the '' modulus'' of the operation.
Given two positive numbers and , mo ...
''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
Euclid's theorem is a fundamental statement in number theory that asserts that there are Infinite set, infinitely many prime number, prime numbers. It was first proven by Euclid in his work ''Euclid's Elements, Elements''. There are several proof ...
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 ''as coprime to ''d''.
The theorem is named after the German mathematician
Peter Gustav Lejeune Dirichlet
Johann Peter Gustav Lejeune Dirichlet (; ; 13 February 1805 – 5 May 1859) was a German mathematician. In number theory, he proved special cases of Fermat's last theorem and created analytic number theory. In analysis, he advanced the theory o ...
, who proved it in 1837.
Examples
The primes of the form 4''n'' + 3 are
: 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'':
: 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.
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 2''d'', if we start with ''n'' = 0. For example, 6''n'' + 1 produces the same primes as 3''n'' + 1, while 6''n'' + 5 produces the same as 3''n'' + 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
by using the following method:
Let
. Then we let
which is prime. We continue by computing
. Because
is of the form
, either 13 or 67 is of the form
. We have that
and is prime, so
. We then continue this process to find successive primes of the form
(Silverman 2013).
Distribution
Since the primes thin out, on average, in accordance with the
prime number theorem
In mathematics, the prime number theorem (PNT) describes the asymptotic analysis, asymptotic distribution of the prime numbers among the positive integers. It formalizes the intuitive idea that primes become less common as they become larger by p ...
, 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
In mathematics, the term "almost all" means "all but a negligible quantity". More precisely, if X is a set (mathematics), set, "almost all elements of X" means "all elements of X but those in a negligible set, negligible subset of X". The meaning o ...
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
In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ot ...
:
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
:
:
:
:
(all except
)
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
In 1737, Euler related the study of prime numbers to what is known now as the Riemann zeta function: he showed that the value
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 polynomial
In mathematics, the ''n''th cyclotomic polynomial, for any positive integer ''n'', is the unique irreducible polynomial with integer coefficients that is a divisor of x^n-1 and is not a divisor of x^k-1 for any Its roots are all ''n''th prim ...
s.
The general form of the theorem was first conjectured by
Legendre in his attempted unsuccessful proofs of
quadratic reciprocity
In number theory, the law of quadratic reciprocity is a theorem about modular arithmetic that gives conditions for the solvability of quadratic equations modulo prime numbers. Due to its subtlety, it has many formulations, but the most standard st ...
— as
Gauss
Johann Carl Friedrich Gauss (; ; ; 30 April 177723 February 1855) was a German mathematician, astronomer, Geodesy, geodesist, and physicist, who contributed to many fields in mathematics and science. He was director of the Göttingen Observat ...
noted in his ''
Disquisitiones Arithmeticae'' — but it was proved by 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 mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Peter Gustav Lejeune Dirichlet's 1837 introduction of Dir ...
.
gave an
elementary proof In mathematics, an elementary proof is a mathematical proof that only uses basic techniques. More specifically, the term is used in number theory to refer to proofs that make no use of complex analysis. Historically, it was once thought that certain ...
.
Proof
Dirichlet's theorem is proved by showing that the value of the
Dirichlet L-function
In mathematics, a Dirichlet L-series is a function of the form
:L(s,\chi) = \sum_^\infty \frac.
where \chi is a Dirichlet character and s a complex variable with real part greater than 1 . It is a special case of a Dirichlet series. By anal ...
(of a non-trivial
character) at 1 is nonzero. The proof of this statement requires some calculus and
analytic number theory
In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Peter Gustav Lejeune Dirichlet's 1837 introduction of Dir ...
. 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 .
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
makes an argument similar to the one made in the proof of
Euclid's theorem
Euclid's theorem is a fundamental statement in number theory that asserts that there are Infinite set, infinitely many prime number, prime numbers. It was first proven by Euclid in his work ''Euclid's Elements, Elements''. There are several proof ...
(Silverman 2013). The proof is given below:
We want to prove that there are infinitely many primes of the form
. Assume, for contradiction, that there are only finitely many primes of the form
. We then compile a list of all such primes
where