Chinese Remainder Theorem with unknown moduli

Question

We are counting intervals of prime width that can be covered by a set of primes. (By covered we mean every element is a multiple of one of primes.)

Formally, Let $p_1, \dots p_n$ be the first $n$ prime numbers and $A=(m_1, \dots, m_{p_{n+1}-1})$ be any arrangement of them, including repetition. [Note $|A| = p_{n+1}-1$]

Is there a solution to the system

\begin{align*} x &\equiv -1 \pmod {m_1 }\\ x &\equiv -2 \pmod {m_2}\\ \vdots \\ x &\equiv -(p_{n+1}-1) \pmod {m_{p_{n+1}-1}}\\ \end{align*}

For example, if we consider the set of primes $(2,3,5,7,11)$ then there are four solutions to the system. One is given by \begin{align*} x &\equiv -1 \pmod {5 }\\ x &\equiv -2 \pmod {2}\\ x &\equiv -3 \pmod {3}\\ x &\equiv -4 \pmod {2}\\ x &\equiv -5 \pmod {7}\\ x &\equiv -6 \pmod {2}\\ x &\equiv -7 \pmod {11}\\ x &\equiv -8 \pmod {2}\\ x &\equiv -9 \pmod {3}\\ x &\equiv -10 \pmod {2}\\ x &\equiv -11 \pmod {5}\\ x &\equiv -12 \pmod {2}\\ \end{align*}

This has solution $x = 168$. Also, if we swap the 7 and 11 above we get $x = 1608$. Each solution corresponds to a different arrangement of the moduli that 'cover' the interval. Once covered the Chinees Remainder Theorem guarantees a solution.

Anyone know of a way to count the number of solutions in the general case?

Answer 1

EDIT: As pointed out in the comments, this is not an answer to the question as intended, but I am still not too clear what that question is. When we finish our discussion, I will delete this answer. (and hopefully write another one? ^.^)

---

The Chinese remainder theorem does not merely give a solution, it proves the uniqueness of that solution, modulo the gcd of the moduli. So whenever the CRT applies, the answer is $1$.

Also worth noting that the CRT is a very general result, and since everything in sight is coprime, the only reason that it does not apply automatically is because it demands only one equation for each modulus. But note that if you have two equations $x \equiv A_1$ and $x\equiv A_2$ with the same modulus, then either they are redundant or inconsistent. Of course if there are ever two inconsistent equations then the number of solutions is zero. If conversely there are no inconsistent equations, then we can eliminate all the redundancies and condense to a system which has only one equation for each modulus.

The only subtlety is that in your setup you allow redundancy, but do not demand "covering". Assuming that was an intended feature of the problem, the CRT still gives you one solution, but only modulo $\gcd(m_1,m_2,\dots,m_{p_{n+1}-1})$; i.e. the product of all the primes that appear at least once. Thus we need only to count the number of [disjoint] intervals of that size that fit into an interval of size $p_1\times\cdots\times p_n$. In other words, the number of solutions is $$\begin{cases} 0 & \text{if any two equations are inconsistent,} \\ p_1\times\cdots\times p_n\times \displaystyle\prod_{p=m_k \text{ for at least one }k} \frac{1}{p} & \text{otherwise.} \end{cases}$$