most recent 30 from http://mathoverflow.net 2013-05-24T02:55:26Z http://mathoverflow.net/feeds/question/77055 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/77055/find-the-least-prime-p-such-that-mn-divides-p-1 Aaron Sterling 2011-10-03T16:43:11Z 2011-10-04T15:24:49Z

<p>My hope is that this question is "trivial," but it is outside my knowledge base, so I'd appreciate some advice.</p> <blockquote> <p>Given positive integers $m$ and $n$, find the least prime $p$ such that $p-1 = mnk$ for some $k \geq 1$.</p> </blockquote> <p>For what I am trying to do, I need an explicit algorithm to find $p$, as opposed to an approximation. Is there a best one known? What is the upper bound on how much larger $p$ might be than $mn$? I am happy to assume that $m$ and $n$ are "sufficiently large" for the algorithm to have nice properties, if that helps.</p> <p>Thank you. Hopefully the answer is obvious to everyone but me. :-)</p>

http://mathoverflow.net/questions/77055/find-the-least-prime-p-such-that-mn-divides-p-1/77056#77056 Igor Rivin 2011-10-03T16:51:06Z 2011-10-03T18:26:05Z

<p>Firstly, I don't understand the point of having both $m$ and $n.$ Since only their product appears, call it $k.$ You are then trying to find the smallest prime congruent to $1$ modulo $k.$ The bound for such is a highly nontrivial matter, see (eg)</p> <p><a href="http://en.wikipedia.org/wiki/Linnik%27s_theorem" rel="nofollow">http://en.wikipedia.org/wiki/Linnik%27s_theorem</a></p> <p><strong>EDIT</strong> It is believed that you don't have to examine more than $\log^2 k$ multiples to find the first prime in a progression of your type.</p>