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.

  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ Thanks! I guess my searching was quite sloppy then :). $\endgroup$ – Srivatsan Sep 5 '11 at 2:08
  • $\begingroup$ 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... $\endgroup$ – Srivatsan Sep 5 '11 at 7:04
  • $\begingroup$ @Srivatsan Narayanan: I support Gerry's answer. Mine is just a silly offhand remark; his points to a major theorem. :) $\endgroup$ – Charles Sep 7 '11 at 4:02
  • $\begingroup$ Is the constant $c$ known as well ? $\endgroup$ – Peter Oct 14 '15 at 18:18
  • $\begingroup$ @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$. $\endgroup$ – 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.

  • $\begingroup$ Oh, that's interesting. Thanks! Is there any conditional result or any explicit conjecture of this vein? $\endgroup$ – Srivatsan Sep 5 '11 at 4:35
  • $\begingroup$ @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. $\endgroup$ – Charles Sep 5 '11 at 4:37
  • $\begingroup$ Ok. Thank you. ${}{}{}{}$ $\endgroup$ – Srivatsan Sep 5 '11 at 4:38
  • $\begingroup$ 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? $\endgroup$ – Dan Brumleve Sep 7 '11 at 3:37
  • 1
    $\begingroup$ @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}$. $\endgroup$ – Charles Sep 7 '11 at 3:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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