# least prime in a arithmetic progression

Hello

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.

-
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 mathoverflow.net/questions/834/…. –  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$. jlms.oxfordjournals.org/cgi/reprint/s2-41/2/193.pdf –  Dimitris Koukoulopoulos Nov 15 '11 at 19:20

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.

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$
-
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 ams.org/journals/mcom/1996-65-216/ 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 math.uiuc.edu/~xiannan/QuaResL1ver2.pdf –  Ho Chung Siu Mar 15 '12 at 7:06