Smallest prime in arithmetic progressions: upper bounds?

This question is inspired by @Dan Brumleve's question on finding Pratt certificates efficiently. In a comment, I say that his problem is as hard as factoring, as long as the following problem is "easy" (i.e., can be solved in polynomial time):

Given $N > 2$, find a prime $p$ such that $$p \equiv 1 \pmod{N} \tag{1}.$$

(Of course, Dirichlet's theorem assures us that infinitely many such $p$ exist.)

Now, I do not know of a clever way to find such a $p$, so I suggested simply iterating through the arithmetic progression $1+kN$ for $k = 0, 1, 2, \ldots$, and terminating when we hit the first prime number. Clearly, this procedure is efficient if and only if the smallest prime $p$ satisfying $(1)$ is at most $N^{O(1)}$. (Edit: This claim is incorrect; see below.) I want to know if such a bound holds or not.

More generally,

Given an integer $N$, what upper bound do we know on the smallest prime satisfying $(1)$?

I did a quick check on Wikipedia and Mathworld, but cannot find any relevant results.

Edit: Turns out the claim in the question is false. The procedure will be efficient only if the smallest prime is $O(N \cdot\mathrm{poly}\log N)$, which seems very unlikely. In any case, I will just keep this question as it is, since it makes sense as a stand-alone question as well.

• I apologize for the mistake (which is only tangentially related to this question anyway), and also not researching the topic properly. I overlooked the link to Linnik's theorem at the bottom of the wiki page. – Srivatsan Sep 5 '11 at 2:39

The relevant results are found under the heading, Linnik's Theorem. Linnik proved that the least prime congruent to $a$ mod $d$ is at most $cd^L$ for some absolute constants $c$ and $L$. The current best bound is $L\le5.2$. On the Generalized Riemann Hypothesis, you can show there's a prime less than $(\phi(d)\log d)^2$, where that's Euler's phi-function. It is conjectured there's always a prime less than $d^2$.

• Thanks! I guess my searching was quite sloppy then :). – Srivatsan Sep 5 '11 at 2:08
• Since a second answer has been posted, I unaccepted your answer for now. I hope you don't mind :). I will accept some answer after a few days... – Srivatsan Sep 5 '11 at 7:04
• @Srivatsan Narayanan: I support Gerry's answer. Mine is just a silly offhand remark; his points to a major theorem. :) – Charles Sep 7 '11 at 4:02
• Is the constant $c$ known as well ? – Peter Oct 14 '15 at 18:18
• @Peter, I don't know. I suppose one could chase through the literature on Linnik's Theorem to see. But since 5.2 is conjectured to be far from best possible for $L$, there may not be so much interest in pinning down a value for $c$. – Gerry Myerson Oct 14 '15 at 22:01

Gerry Myerson has answered your main question, so I'll address the other part. I don't think that the claim is false, though certainly it's not proven. In any case I wouldn't say it's "very unlikely".

In fact it seems quite likely to me that the smallest k with $kn+1$ prime will be $O((\log n)^3)$ -- indeed, probably even $O((\log n)^2(\log\log n)^e)$ for some e.

Disregarding $n<20$, $e=0.18$ works up to 30 million with a constant of 1. A braver mathematician might conjecture that it holds for $e=0$ and a somewhat larger constant.

• Oh, that's interesting. Thanks! Is there any conditional result or any explicit conjecture of this vein? – Srivatsan Sep 5 '11 at 4:35
• @Srivatsan Narayanan: I do not know of a conditional proof. I'm sure there's a conjecture on the subject--older than mine, that is--but I haven't found it in a cursory search. – Charles Sep 5 '11 at 4:37
• Ok. Thank you. ${}{}{}{}$ – Srivatsan Sep 5 '11 at 4:38
• Charles' conjecture is similar to Cramér's conjecture, generalized to arithmetic progressions, but concerning only the first gap; the same heuristic arguments apply. One thing I don't understand is why the log(log(n))^e term? – Dan Brumleve Sep 7 '11 at 3:37
• @Dan Brumleve: I'm quite confident that for every $\varepsilon>0$ there are only finitely many prime gaps larger than $(\log x)^{2+\varepsilon}$ but Maier's (1985?) paper shook my confidence in the Cramer model enough that I question not just $(\log x)^2$ but even $C(\log x)^2.$ (I wouldn't bet money that it fails for $C=2$, but it wouldn't shock me.) This problem is similar: I'm not confident enough on a theoretical or computational basis to say $(\log n)^2$. But in this case I opted for the slightly stronger form $(\log n)^2(\log\log n)^e$ rather than just $(\log n)^{2+\varepsilon}$. – Charles Sep 7 '11 at 3:58