Find the least prime \$p\$ such that \$mn\$ divides \$p-1\$ - MathOverflow 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 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 Answer by Igor Rivin for Find the least prime \$p\$ such that \$mn\$ divides \$p-1\$ 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>