# Dirichlet's theorem

It is easy to prove that there are infinitely many primes in the arithmetic sequence 1, 5, 9, 13, 17,... (an=4n+1), but only one in the similar sequence 2, 6, 10, 14, 18,... (an=4n+2).  An obvious guess is that there must be infinitely many primes in the sequence a+nb (n=1,2,3...) if a and b are relatively prime (and only finitely many otherwise).  Dirichlet proved this was indeed the case in 1837 by proving the following.
Dirichlet's Theorem on Primes in Arithmetic Progressions
If a and b are relatively prime positive integers, then the arithmetic progression a, a+b, a+2b, a+3b, ... contains infinitely many primes.
Recall the prime number theorem states that there are asymptotically n/log(n) primes less than n.  It has been proven that these sequences contain asymptotically n/(phi(a) log n) primes less than n.

A great deal of effort has been spent trying to find a reasonable limit by which the first prime in such a sequence must occur.  See Linnik's constant for one approach to finding such a bound.