MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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,

share|cite|improve this question
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
up vote 8 down vote accepted

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.)

share|cite|improve this answer
If one assumes GRH, then one can obtain much stronger results: see, e.g. Corollary 1.2 of, 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
Xylouris has 5.18 in Xylouris, Triantafyllos, On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions, Acta Arith. 150 (2011), no. 1, 65–91, MR2825574 (2012m:11129). – Gerry Myerson Aug 14 '14 at 23:25
@GerryMyerson: Right, but as far as I know the 5.00 is unpublished. – Charles Aug 14 '14 at 23:56
I found Xylouris' thesis online: – GH from MO Aug 15 '14 at 0:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.