Dirichlet's theorem

Dirichlet's theorem states:

There are infinitely many prime numbers in an arithmetic progression of the form a_n + b if a and b are relatively prime (i.e., (a, b) = 1)).

For example, the sequence of numbers which are one more than a multiple of 11 (1, 12, 23, 34, 45, ...) is an arithmetic progression. Dirichlet's theorem states that this sequence contains infinitely many prime numbers. Equivalently, there are infinitely many values of k for which 11*k+1 is a prime number.

The requirement that a and b be relatively prime is crucial: if a and b share a common factor k, we can write a = k*c, b=k*d. Then an+b = kcn+kd=k(cn+d) If k is not equal to 1, then this has two factors unless cn+d = 1, so n=0 and d=1. The case n=0 corresponds to the first term, and so only the first term of such a sequence may be prime. For example, the arithmetic sequence of integers of the form 12k+2 contains only even numbers, and thus no primes except 2.

Gauss proposed this conjecture but could not prove it. Dirichlet first proved this in 1837 using the Dirichlet L-series. The proof is quite challenging to understand, and is beyond the scope of most number theory courses.