## Find the least prime $p$ such that $mn$ divides $p-1$

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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. :-)

-

1
When you write "for $k\ge1$", do you mean "for some $k\ge1$" or "for every $k\ge1$" ?:-( – Chandan Singh Dalawat Oct 4 2011 at 3:11
@Chandan Singh Dalawat: I mean some $k$, in fact the smallest possible $k$. Now edited. – Aaron Sterling Oct 4 2011 at 15:24

## 1 Answer

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.

-

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 3 2011 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 3 2011 at 18:08
Thanks, both of you, this is a big help. – Aaron Sterling Oct 3 2011 at 18:14
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. – quid Oct 3 2011 at 18:22

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 3 2011 at 18:57
show 10 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 27, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9443293809890747, "perplexity_flag": "middle"}