Solving system of modulo inequalities?

340 Views Asked by At

I've already asked similar question, but back then I didn't know about modulo arithmetic.

I think I can ask it more clearly now.

Is this type of system of equations solvable? If yes, how? $$ \begin{split} x \mod p_1 & < x \mod q_1\\ x \mod p_1 & < x \mod q_2\\ x \mod p_1 & < x \mod q_3\\ \vdots & \\ x \mod p_1 &< x \mod q_m\\ \\ x \mod p_2 &< x \mod q_1\\ x \mod p_2 &< x \mod q_2\\ x \mod p_2 &< x \mod q_3\\ \vdots &\\ x \mod p_2 & < x \mod q_m\\ \\ \vdots & \\ \\ x \mod p_n &< x \mod q_1 \\ x \mod p_n &< x \mod q_2 \\ x \mod p_n &< x \mod q_3 \\ \vdots &\\ x \mod p_n &< x \mod q_m \\ \end{split} $$ where $p$ and $q$ are all different prime numbers.

And if this system is solvable what is $x$?

You can also use the relation $\leq$ instead of $<$ in the inequalities above, if this simplifies the problem.

1

There are 1 best solutions below

5
On

As asked in fleablood's question comment, it seems from the question context you're using $\bmod$ to refer to the non-negative remainder on division, e.g., $a = (b \bmod c)$ means $b = kc + a$, where $k$ is an integer, $c$ is positive integer and $0 \le a \lt c$. I'm going to assume this. Also, if so, then note there's no unique answer for $x$, although you can always do something like choose the smallest possible positive value as being the value you want..

To keep the discussion simpler, I'm also going to assume all $p_i$ and all $q_i$ are distinct. In that case, you can have

$$x \equiv y_1 \pmod{\prod_{i=1}^{n}p_i}, \; 0 \le y_1 \lt \min(p_1, p_2, \ldots, p_n, q_1 - 1, q_2 - 1, \ldots, q_m - 1) \tag{1}\label{eq1A}$$

$$x \equiv y_2 \pmod{\prod_{i=1}^{m}q_i}, \; y_1 \lt y_2 \lt \min(q_1, q_2, \ldots, q_m) \tag{2}\label{eq2A}$$

The first equation comes from that $x \equiv y_1 \pmod{\prod_{i=1}^{n}p_i}$ means $x \equiv y_1 \pmod{p_i}$ for all $i$, and similarly for the second equation. The limits on $y_1$ and $y_2$ ensure they will be equal to the remainder when divided by $p_i$ and $q_i$, respectively, and $y_1 \lt y_2$ to meet the question inequality conditions.

Note although \eqref{eq1A} and \eqref{eq2A} don't necessarily encompass all possible solutions, at least with these $2$ modular equations you have the Chinese remainder theorem guaranteeing a solution always exists.

An example which works in all cases is $y_1 = 0$ and $y_2 = 1$, i.e.,

$$x \equiv 0 \pmod{\prod_{i=1}^{n}p_i} \tag{3}$$

$$x \equiv 1 \pmod{\prod_{i=1}^{m}q_i} \tag{4}$$