# Using CRT to find arbitrarily long gaps between primes

It is straight forward to find a gap between primes that consists of at least $2n$ using only the Chinese Remainder Theorem.

Let $p_n$ be the $n$th prime.

Find $x$ such that:

$$x \equiv -1 \pmod 2$$

$$x \equiv -2 \pmod 3$$

$$x \equiv -4 \pmod 5$$

$$x \equiv -6 \pmod 7$$

$$x \equiv -8 \pmod {p_5}$$

$$\dots$$

$$x \equiv -{2n} \pmod {p_{n+1}}$$

Clearly, not every condition is needed for the gap. For example, $x\equiv -8 \pmod {3}$ so we could find a gap of at least $2n$ using CRT with less than $n+2$ distinct primes.

Limiting a set of equations such that every condition is needed for the gap size, it occurs to me that finding a prime gap of at least $2*p_{n}$ using CRT only need involve $n+2$ conditions each with distinct primes.

For example, a prime gap of at least $2*p_{5}=22$ can be found using the following $7$ conditions:

$$x \equiv -1 \pmod 2$$ $$x \equiv -2 \pmod 3$$ $$x \equiv -4 \pmod 7$$ $$x \equiv -6 \pmod 5$$ $$x \equiv -10 \pmod {11}$$ $$x \equiv -12 \pmod {13}$$

Using CRT, I find that $x = 9439$ which is prime and has a gap of $9461-9439 = 22$

To show how I came up with these set of conditions, let me use the following notation:

$$\#-\#-\#-\dots$$

to characterize the least prime factor of each odd integer in the gap which is not a prime.

In the above example, the gap of size $22$ consists of $10$ odd integers in the following order:

$$3-7-5-3-11-13-3-5-7-3$$

Finding a gap of $p_n$ consists of finding a set of $n+2$ CRT conditions that characterize this sequence. For example, I can find a gap of at least $26$ using $8$ distinct conditions based on these $12$ odd integers:

$$11-3-7-5-3-13-17-3-5-7-3-11$$

It occurs to me that this approach will work for any $p_n$ using $n+2$ distinct primes as long as $2$ of the primes are greater or equal to $p_n$ and the order of the all but these two primes are the least prime factors in reverse natural order. Natural order of the odd integers for the above would be: $3,5,7,9,11$ with the least prime factors being $3,5,7,3,11$. Reverse natural order of the least prime factors is therefore: $11,3,7,5,3$.

Here's my question:

Does it follow that this method delivers the minimum number of distinct prime factors involved with a gap size of $2p_n$ or larger?

It seems to me that the answer is yes.

Let $f(m,p_n)$ be the number of distinct primes $p$ where $p < p_n$ and there exists $x$ such that $m < x \le (m+2*p_n)$ and $p$ is the least prime factor of $x$.

Does it follow that $f(m,p_n) \ge n+2$? Is there a counter example where $f(m,p_n) < n+2$?

Edit 1:

I found a counter example for my second question. In the case of $p_n=23$, $2*f_7(0,22) = 2$ but $f_7(76,122)=3$

Based on this, I am updating my question to just ask if there is an example of a prime gap that involve $n+1$ or less distinct least prime factors in the sequence of non-primes but is still $2p_n$ or larger.