3

My hope is that this question is "trivial," but it is outside my knowledge base, so I'd appreciate some advice.

Given positive integers $m$ and $n$, find the least prime $p$ such that $p-1 = mnk$ for some $k \geq 1$.

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.

Thank you. Hopefully the answer is obvious to everyone but me. :-)

Aaron Sterling
  • 881

1 Answers1

10

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)

http://en.wikipedia.org/wiki/Linnik%27s_theorem

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

Igor Rivin
  • 95,560
  • 2
    The question asks for an algorithm. The algorithm will be to test all numbers of the form $mns+1$, for $s=1,2,\ldots$ for primality, using e.g., AKS (or something faster and probabilistic like Miller-Rabin). I don't think there is anything else you can do, as there are no simple ways of generating primes. The running time of this algorithm depends on the smallest prime that you meet and for that see Igor's answer. – Felipe Voloch Oct 03 '11 at 17:56
  • @Felipe: Yes, thank you. I meant (implicitly) that you should test all the numbers until the bound, but it is much better to be explicit. (although the OP does also ask for the bound explicitly) I suppose that theoretically there could be a better algorithm then testing all the multiples, but I am pretty sure no one knows what it is. – Igor Rivin Oct 03 '11 at 18:08
  • It might help to do some pre-sieving first, Eratostenes-like. Eg, if mn is odd there is no point in testing the odd multiples of mn; and make similar considerations for all other 'small' primes. –  Oct 03 '11 at 18:22
  • @quid: true, but for any "reasonable" value of $k = mn,$ $\log^2 k$ is quite small (I suppose where reasonable means: small enough so you can test for primality). – Igor Rivin Oct 03 '11 at 18:27
  • @Igor: The reason I wrote $mn$ instead of a single value is that I had in the back of my mind another problem, which is: given $m$ and $n$, find the least prime $p$ such that $p-1=(m+i)(n+j)$ for $i,j \geq 1$. So the smallest "rectangle" of area $p-1$ that contains the rectangle $mn$. I don't know if that is a related problem, or merits a question on its own, still pondering that. I figured I should comment in case you (or someone else) knew the answer offhand. – Aaron Sterling Oct 03 '11 at 18:42
  • Sorry, I did not see your edit before. But then I also do not understand it; dshould it follow from Linnik-like results or is this something specific. It was my understanding (possibly in error) that people believe Linnik's constant is 2 so about a bound of d^2 leaving room for about d terms; i.e. mn. However, on second thought I agree that depending on how one sets up the primality testing the sieving I mention might not be that relevant. What I mean is if one uses a standard prime-testing-program it will do trial divison anyway at the start and chatch just those composites very quickly. –  Oct 03 '11 at 18:43
  • 1
    @quid: the $\log q^2$ is apparently a heuristic estimate due to Wagstaff. And you do have a good point about sieving: sieving wants to find many primes, here you are looking for one, so it might or might not help, depending on various subtleties... – Igor Rivin Oct 03 '11 at 18:57
  • @Aaron: so you want to find the least prime such that $p-1$ factors into two factors, one at least $m$ and the other at least $n$? – Igor Rivin Oct 03 '11 at 18:59
  • @Igor: yes, exactly. – Aaron Sterling Oct 03 '11 at 19:01
  • @Igor: thank you for the information. It seems I was in error. –  Oct 03 '11 at 19:10
  • For the problem of finding the smallest prime p such that p-1 has two factors, one larger than n and one larger than m, one should sift out candidates from a 2-d array of numbers indexed by the potential factors greater than m respectively n. A cool thing about this arrangement is that if ij+1 is divisible by a small prime q, then so is (i+q)j+1, so one can avoid testing many pairs by doing simple sieving. Gerhard "Ask Me About System Design" Paseman, 2011.10.03 – Gerhard Paseman Oct 03 '11 at 20:02
  • @Gerhard: the second problem is certainly more tractable than the first, but I wonder whether one can find any reasonable estimate on what the smallest solution is... – Igor Rivin Oct 03 '11 at 20:28
  • There are reasonable conjectures. Note that the scheme I suggest is a union of artihmetic progressions, and so one can likely find an answer within nm entries. But I'm not just guessing here, I'm guessing using other's guesses as well. I hope Aaron Sterling or another reader becomes motivated enough to run some simulations and tell us the results. Gerhard "Ask Me About System Design" Paseman, 2011.10.03 – Gerhard Paseman Oct 03 '11 at 20:53
  • Thanks very much, everyone. I formally asked a question about this second issue, because it sounds nontrivial. – Aaron Sterling Oct 04 '11 at 15:31