 Holetaug

2022-07-10

Solving system of modulo inequalities. Is this type of system of equations solvable? If yes, how?
$\begin{array}{rl}x\phantom{\rule{1em}{0ex}}\mathrm{mod}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}{p}_{1}&
where $p$ and $q$ are all different prime numbers.
And if this system is solvable what is x? Nicolas Calhoun

It seems from the question context you're using $mod$ to refer to the non-negative remainder on division, e.g., $a=\left(bmodc\right)$ means $b=kc+a$, where $k$ is an integer, $c$ is positive integer and $0\le a. 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
$\begin{array}{}\text{(1)}& x\equiv {y}_{1}\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}\prod _{i=1}^{n}{p}_{i}\right),\phantom{\rule{thickmathspace}{0ex}}0\le {y}_{1}
$\begin{array}{}\text{(2)}& x\equiv {y}_{2}\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}\prod _{i=1}^{m}{q}_{i}\right),\phantom{\rule{thickmathspace}{0ex}}{y}_{1}<{y}_{2}
The first equation comes from that $x\equiv {y}_{1}\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}\prod _{i=1}^{n}{p}_{i}\right)$ means $x\equiv {y}_{1}\phantom{\rule{0.444em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}{p}_{i}\right)$ 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}<{y}_{2}$ to meet the question inequality conditions.
Note although (1) and (2) 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.,
$\begin{array}{}\text{(3)}& x\equiv 0\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}\prod _{i=1}^{n}{p}_{i}\right)\end{array}$
$\begin{array}{}\text{(4)}& x\equiv 1\phantom{\rule{1em}{0ex}}\left(\mathrm{mod}\phantom{\rule{0.333em}{0ex}}\prod _{i=1}^{m}{q}_{i}\right)\end{array}$

Do you have a similar question?