Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
    
(Someone downvoted two of my questions in quick succession.) @downvoter Please explain the downvote. –  Srivatsan Sep 11 '11 at 16:14
    
@Charles I am reasonably sure. I can see the downvotes in the questions, and I confident they weren't there earlier. Anyway, thanks for the information. –  Srivatsan Sep 11 '11 at 19:15

2 Answers 2

up vote 10 down vote accepted

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

share|improve this answer
    
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

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.

share|improve this answer
    
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
1  
@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

Your Answer

 
discard

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.