Dirichlet's theorem (another Prime Pages' Glossary entries)
 Glossary: Prime Pages: Top 5000: The hardware and software on this system was updated September 4th.  Please let me know of any problem you encounter. 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. See Also: LinniksConstantRelated pages (outside of this work) Dirichlet's Theorem (includes an estimate of how many primes)MathWorld's Linnik's Constant How large is the first prime in an arithmetic sequence? Chris K. Caldwell © 1999-2014 (all rights reserved)