# Dirichlet's Theorem on Primes in Arithmetic Progressions

Often we are asked a question starting "are there any primes of the
form ... ?" One of the classic ways to finish that question is "*ak*+*l*"
where *k* and *l* are fixed integers, and *a* takes on
the values 0, 1, 2, ... . For example, if *k* is 4 and *l* is
1, we are asking are there infinitely many primes in the following list?

We see several already, so we might guess that there are. But what if *k*
is 4 and *l* is 2, then we are asking are there infinitely many primes
in the following list? t

Obviously not! In fact it is a trivial exercise to prove that if there is
more than one prime in the arithmetic sequence generated by *k* and
*l*:

*l*,

*l*+

*k*,

*l*+2

*k*,

*l*+3

*k*,

*l*+4

*k*, ... ,

then *k* and *l*, are relatively prime (i.e., there is no positive
integer that divides both *k* and *l* except 1). But is this relatively
prime condition enough to guarentee infinitely many primes? Dirichlet answered
yes over 150 years ago by proving the following.

Dirichlet's Theorem on Primes in Arithmetic Progressions(1837)If

kandlare relatively prime positive integers, then the arithmetic progressioncontains infinitely many primes.l,l+k,l+2k,l+3k, ...

Often knowing that there are infinitely many primes is enough, but sometimes
we need more information--perhaps an estimate of how many are less than
or equal to *n* for any given *n* (such as the prime number theorem gives in the
case *k*=1). When the prime number theorem was proved, it then followed
that

It is possible to give error estimates such as the following.

This was proved, for example, with *a*=1/15 [Walfisz63].