# Find the least prime so that p-1 has two factors greater than $m$ and $n$

Given positive integers $m$ and $n$, what is an explicit upper bound on the least prime $p$ such that $p-1$ has factors $m+i$ and $n+j$ for some $i,j \geq 0$? In other words, some number at least as large as $m$ divides $p-1$, and so does some number at least as large as $n$.

Example:

Suppose $m=5$ and $n=4$. Then, while 23 is prime, and $23 > 20$, it does not qualify because 22 can only be factored into 11 and 2, and $2< m,n$. On the other hand, 29 is ok, because 28 can be factored into 7 and 4, both of which are at least as large as $m,n$.

• Do you really mean the question as you pose it? I thought you wanted $p-1 = (m+i)(n+j)?!$ – Igor Rivin Oct 4 '11 at 15:34
• Hmm... I wish to find the smallest $p$ for which this is true of any $i$ and $j$. So $i$ and $j$ "don't matter." I will add an example to the question. – Aaron Sterling Oct 4 '11 at 15:38
• You should improve the title of your question. – Someone Oct 4 '11 at 15:49
• @Someone: hahaha!!! Yes, you have a point. Better now? – Aaron Sterling Oct 4 '11 at 15:51
• I think you want (p-1) to be the product of two numbers, each sufficiently large. Otherwise any prime p > max(n,m) will have a factor of p-1 larger than both m and n, and any p > 2max(n,m) will have one factor bigger than twice n and another bigger than m. You might also borrow with attribution my and quid's and Igor's comments about the product version of your problem, which is what I suspect you really want. Gerhard "Ask Me About System Design" Paseman, 2011.10.04 – Gerhard Paseman Oct 4 '11 at 15:55