# Smallest prime in an arithmetic progression

Let $\{a_n\}_{n\in\mathbb{N}}$ be defined as $a_n = a + bn$ for some $a, b >0,(a, b) = 1$. Are there good bounds on the minimal $k$ s.t. $a_k$ is prime. It is well known that there are infinitely many primes in this series,

-
Search under Linnik's constant. Linnik showed that the least such prime is bounded by $\ll b^{L}$ for a constant $L$, which has been improved over the years, most recently by Xylouris. – Lucia Aug 14 '14 at 17:46

This is Linnik's theorem, and the best known bound is $O(b^5)$ due to Xylouris. (This is in the Wikipedia page, and as I admitted in this year's JMM I added it to the Wikipedia page. It's in his thesis but otherwise unpublished as far as I know.)
If one assumes GRH, then one can obtain much stronger results: see, e.g. Corollary 1.2 of arxiv.org/abs/1309.3595, which shows the strict bound $(\phi(b) \log b)^2$. – Peter Humphries Aug 14 '14 at 18:46
And it is conjectured that much more that even what can be proved using GRH is true, namely that the first prime is O(b^{1+\epsilon}) for all $\epsilon>0$, or perhaps even $O(b \log^2b)$. – Joël Aug 14 '14 at 21:03