MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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


Here I want to consider the simplest arithmetic progression $n\equiv 1\pmod{q}$ where $q$ is a prime. Is it true that we can find a prime $p\leq q^2$ in this arithmetic progression?

This question is usually asked for any $q$ instead of only prime value $q$, but I think if one restrict to only prime number $q$ Linnik bound would be easier to compute. Am I right?

Thank you.

share|cite|improve this question
It's a reasonable hope ... but I do not know of any way to use the fact that the modulus is prime or that the progression starts at 1 to improve any known bounds. In fact, one could argue that both hurt your chances: $q$ being prime means that the primes are distributed among more residue classes modulo $q$, reducing the number in any one residue class; and results on "prime number races" say that primes are slightly less likely to be squares modulo $q$ (such as 1) than non-squares. – Greg Martin Nov 14 '11 at 6:50
Dear M.B., it is funny that you ask this question right now. T. Xylouris, a colleague of mine in Bonn, has proved a result about this in 2009 - this is mentioned in the answer by Will - and he has still been working on it. I do not know the current state of his research, but his thesis defence on precisely that topic is the day after tomorrow. – Robert Kucharczyk Nov 14 '11 at 11:02
It is believed that the least prime congruent to $a\pmod q$ is $\ll_\epsilon q^{1+\epsilon}$, and maybe even $\ll q(\log q)^{1+o(1)}$. The underlying heuristic is that the probability that all integers $n\le Q$ in the arithmetic progression $a\pmod q$ are not prime is $\prod_{n\le Q,n\equiv a\pmod q}(1-1/\log n)\approx (1-1/\log q)^{Q/q}$. This becomes $<1$ as soon as $Q\gg q\log q$. You can play with this quite a bit (e.g. consider only integers with no primes $\le(Q/q)^{1/3}$, and so on). See also…. – Dimitris Koukoulopoulos Nov 15 '11 at 19:04
Maybe the right answer is $Q\ll\phi(q)\log^2q$: let $N$ be the set of $n\le Q$, all of whose prime factors are $<Q^\epsilon$, and which lie in the arithmetic progression $a\pmod q$. Then $N$ should contain a prime as soon as $Q\gg\phi(q)\log^2q$. – Dimitris Koukoulopoulos Nov 15 '11 at 19:20

EDIT, September 2015. This material has come up again. Note that, in post and comments, i simply report things I found. I also did a computer program because I was curious about what might be the best possible behavior. It is probably time for a follow-up question.

Odd. There is an article about this in the October M.A.A. Monthly, pages 737-742, by R. Thangadurai and A. Vatwani. They give an elementary argument to show $$ p \leq 2^{\phi(q) + 1} - 1.$$ The best unconditional result they report is T. Xylouris (2009), $$ p \leq c_1 q^{5.2}$$ which improves a 1992 result of Heath-Brown.

Apparently Oesterle showed that GRH implies $$ p \leq 70 q (\log q)^2 $$ which is much better. This was a private communication to the authors, not in the reference list.

EDIT TOOOOO: there is some doubt now, BACH and SORENSEN say, on their page 1718 (second page of the downloadable pdf) that Oesterle proved something different in 1979, also never published it. So perhaps the best GRH bound is theirs, $$ p \leq (1 + o(1)) (\phi(q) \log q)^2.$$ Perhaps Xylouris has also worked on this aspect.

Anyway, table of contents at CONTENTS

EDIT: I ran a little computer program for the GRH result, dropping the factor of 70... It certainly appears that the largest prime $q$ for which $ p > q (\log q)^2 $ is $q=5227$ with first prime congruent to $1\pmod q$ being $p=397253 = 1 + 76 \cdot 5227.$ Unprovable. Program run for $q < 10000000$ and print out only $ p > 0.8 \, q \, (\log q)^2. $ Each line is $q, \, p, \, p / \left( q \, (\log q)^2 \right)$

jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./primes_in_progressions 
             2           3    3.12205
             3           7    1.93325
             5          11    0.849326
             7          29    1.09409
            19         191    1.15951
            31         311    0.850749
           227        5449    0.815642
           521       16673    0.817744
          3833      229981    0.881247
          5227      397253    1.03683
          6637      424769    0.82637
        138163    15750583    0.813731
        170167    24504049    0.992619
        177791    22757249    0.875941
        218531    27534907    0.833558
        325517    44921347    0.856523
        326617    42460211    0.806441
        707467   110364853    0.859855
       1940777   326050537    0.801413
       4722079  1104966487    0.99082
       8195953  1753933943    0.84445
    jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ 
share|cite|improve this answer
but $2^{\varphi(q)}$ is much bigger then $q^2$. So do you know if one can get a better bound then $2^{\varphi(q)}$ assuming $q$ is a prime? – M.B Nov 14 '11 at 5:19
I do not know. The article makes special mention of results with remainder 1, as you ask, but they say nothing special about $q$ prime. They made some effort for completeness, so I would say your best result is Xylouris (2009). – Will Jagy Nov 14 '11 at 5:25
Two quick comments. It's maybe interesting to note that for prime $q$, it's easy to establish the Monthly bound: Any prime divisor $p$ of $2^q-1$ works. Also, I'm skeptical of the bound attributed to Oesterle. I'd wager that the best bounds, on ERH, are those in Note that their upper bound is bigger than $q^2$, and so doesn't settle the OP's problem. The discussion in this paper also suggests the result attributed to Oesterle is based on a misunderstanding or a typo. – so-called friend Don Nov 14 '11 at 20:24
@Will Jagy: I believe that it should be $70q^2\log^2 q$ rather then $70q\log^2 q$. The former follows from GRH, whereas the later, an improvement to something of the form $q^{1+\delta}$ for any $\delta$, is only conjectured, and if proven would be a very strong result. – Eric Naslund Nov 22 '11 at 23:03
In fact, the Bach-Sorenson bound has been improved. See – Ho Chung Siu Mar 15 '12 at 7:06

One can clearly improve the L if one restricted the modulus q to prime numbers, however not anywhere near L=2 or so. E.g. in Heath-Brown's article 1992, it's mentioned how you get better results if q has bounded cube-part (i.e. if every prime number p, such that p^3 | q, is less then c1, then there is a c2=c2(1), such that p <= c2 * q^L. Here, the L will be a slightly better constant than if you don't use the assumption of the bounded cube-part, maybe something like 4.5 instead of 5.5, compare a note of "Meng").

The reason for this improvement is, that you have better bounds for character sums (to modulo q) due to Burgess, if you restrict q e.g. to primes (compare §2 of Heath-Brown's 1992 article). Improvement of these bounds then directly translate into improvements of zero-free regions for Dirichlet L-functions (modulo q).

As regards the thought if it would be easier if one restricted oneself only to one residue class, e.g. a mod q where the number a is fixed and q runs, I don't think you can gain something since everything you prove for a fixed a might likely be proven for any other a as well. That thought stems from looking at the proof of Linnik's theorem (meaning the classical proof, there are also some others out there, originating more from sieve theory; I don't know if they would give a different answer but I would be surprised): The whole reasoning is very "symmetric" for whatever a you take. It's not like your average proof in elementary prime number theory (or sieve theory), where you work with a particular sequence a+kq and have sums over different values etc.

Hope this helps.

share|cite|improve this answer

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.