Dirichlet's theorem (another Prime Pages' Glossary entries) Glossary: Prime Pages: Top 5000: GIMPS has discovered a new largest known prime number: 282589933-1 (24,862,048 digits)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-2019 (all rights reserved)