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

2011-10-04T15:30:38Z

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

Answer by Gerhard Paseman for Find the least prime so that p-1 has two factors greater than $m$ and $n$

2011-10-04T18:43:39Z

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

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

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

Answer by Gerhard Paseman for Find the least prime so that p-1 has two factors greater than $m$ and $n$