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

There are comments related to this question in the previous question I asked about prime numbers.

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

## 1 Answer

Here is a suggestion for a problem related to the one you are asking. I will give the two dimensional version; perhaps Joseph O'Rourke will be intrigued enough to illustrate this or a 3 or higher dimensional version for us.

I will suggest a coloring/labeling for an integer grid, with x and y coordinates being all integers greater than m respectively n. I recommend m=1 and n=1 ranging up to 40, but you can choose differently depending on your graph paper. Also, you can decide whether to take advantage of symmetry or not and restrict yourself (or not) to the region x <= y.

Each coordinate (x,y) will be assigned the integer xy+1, but do not label every such coordinate. Instead, use whatever color scheme to sieve out nontrivial multiples of 2 (meaning x and y are both odd, and xy>1), interesting multiples of 3 (those pairs where xy = 2 mod 3 and xy >2), big multiples of 5, and so on, not forgetting to mark the primes encountered. That is, label a coordinate (x,y) with xy + 1 only if that quantity is prime.

You will end up with a colored grid, with the colors having a pleasing pattern (I think) and a look up chart for small m and n of primes greater than mn, where you look at or above and to the right (if you use my orientation) of the coordinate (m,n) for such primes, and try to find the smallest one of the nearest such primes. From generating such a chart for various m,n, you may get a sense of how close heuristically your desired prime is. I predict the value of the smallest such prime p(mn)= 1 + (m+i)(n+j) for nonnegative i and j satisfies p(mn) < (n+m)*m*n for positive integers m,n.

Gerhard "Ask Me About Prime Guesses" Paseman, 2011.10.04

• Although Linnik's theorem and related heuristics does not apply directly, one can consider a "path" composed of two arithmetic sequences from mn+1 to (m+i)(n+j) + 1, and perhaps come up with a better upper bound like 4mn for the value of p(mn). Gerhard "Asl Me About System Design" Paseman, 2011.10.04 – Gerhard Paseman Oct 4 '11 at 18:49