# Minimum $k$ for which every positive integer of the interval $(kn, (k+1)n)$ is divisible by at least one prime number less than $n$

As a continuation of this question relating the Minimum $$k$$ for which every positive integer of the interval $$(kn, (k+1)n)$$ is composite and this other one on the divisibility of numbers in intervals of the form $$(kn, (k+1)n)$$, I have been looking for strategies to prove the following

Conjecture:

The minimum $$k$$ for which every positive integer of the interval $$(kn, (k+1)n)$$ is divisible by at least one prime number less than $$n$$ is greater than $$n+2$$.

Indeed, numerical evidence shows that this conjecture could be strengthened, and even set some kind of exponential lower bound for some $$n>N_0$$. I have looked for the minimum $$k$$ for $$2\leq n< 50$$, and these are the results:

$$n = 8, k = 25$$

$$n = 12, k = 182$$

$$n = 13, k = 168$$

$$n = 14, k = 156$$

$$n = 16, k = 590$$

$$n = 17, k = 1210$$

$$n = 18, k = 1546$$

$$n = 19, k = 3658$$

$$n = 20, k = 238$$

$$n = 21, k = 695$$

$$n = 22, k = 5949$$

$$n = 23, k = 58$$

$$n = 24, k = 2502$$

$$n = 25, k = 2096$$

$$n = 26, k = 15738$$

$$n = 27, k = 2224$$

$$n = 28, k = 52552$$

$$n = 29, k = 5209$$

$$n = 30, k = 159528$$

$$n = 31, k = 60794$$

$$n = 32, k = 22408$$

$$n = 33, k = 267185$$

$$n = 34, k = 80438$$

$$n = 35, k = 173632$$

$$n = 36, k = 168809$$

$$n = 37, k = 73916$$

$$n = 38, k = 202701$$

$$n = 39, k = 179643$$

$$n = 40, k = 151928$$

$$n = 41, k = 170880$$

$$n = 42, k = 890187$$

$$n = 43, k = 162932$$

$$n = 44, k = 159229$$

$$n = 45, k = 643815$$

$$n = 46, k = 152306$$

$$n = 47, k = 727429$$

$$n = 48, k = 220918$$

$$n = 49, k = 697738$$

There is no solution for $$n=2,3,4,5,6,7,9,10,11,15$$ (that is why these solutions are not listed). It seems that there do exist solutions for the rest of values of $$n$$ excepting the ones listed.

First question

How can we prove that indeed those are the only values of $$n$$ for which it does not exist a minimum $$k$$ for which every positive integer of the interval $$(kn, (k+1)n)$$ is divisible by at least one prime number less than $$n$$?

It can be seen that the conjecture holds for all $$2\leq n < 50$$, and that in most cases the minimum $$k$$ for which every positive integer of the interval $$(kn, (k+1)n)$$ is divisible by at least one prime number less than $$n$$ is exponentially greater than $$n$$. However, I have not been able to derive a proof of the Conjecture.

The most promising approach seemed (and seems, AFAIK) to make some smart use of the Chinese Remainder Theorem and the Extended Euclidean algorithm. The solution obtained using the Chinese Remainder Theorem is always of the kind $$x= y \mod \prod_{p where $$y>n+2$$. The problem is that we have also that $$y > \prod_{p and is not the least particular solution of the system of congruences, so if we set $$y = z \mod \prod_{p it would be needed to show that $$z>n+2$$.

I do not know if this is possible / feasible, or if there are other possible approaches to prove the conjecture. So here it is my (twofold) second question:

Second question

Is it possible to prove the conjecture making some smart use of the Chinese Remainder Theorem and the Extended Euclidean algorithm? Are there other possible approaches to prove the conjecture?

• For large $n$ , say from $n=1\ 000$ on , $k$ will explode since we need a prime gap with difference at least $n$ as a necessary condition. If the interval contains a single prime , it cannot do the job. The first occurence of a prime gap with minimum difference $n$ is conjectured to be exponentially larger than $n$ Mar 29 at 10:11
• @Peter agree; however, they do exist prime gaps with difference $n$ such that the primes are less than $n^2$ for some $n$; for instance, $(7,11),(23,29),(113,127)$; although I conjecture that those are the only ones. Mar 29 at 11:16