Solving system of modulo inequalities. Is this type of system of equations solvable? If yes, how? x mod p 1 &lt; x mod q 1 x mod p 1 &lt; x mod q 2 x mod p 1 &lt; x mod q 3 ⋮ x mod p 1 &lt; x mod q m x mod p 2 &lt; x mod q 1 x mod p 2 &lt; x mod q 2 x mod p 2 &lt; x mod q 3 ⋮ x mod p 2 &lt; x mod q m ⋮ x mod p n &lt; x mod q 1 x mod p n &lt; x mod q 2 x mod p n &lt; x mod q 3 ⋮ x mod p n &lt; x mod q m where p and q are all different prime numbers.And if this system is solvable what is x?

Question

Solving system of modulo inequalities. Is this type of system of equations solvable? If yes, how?                    x                mod                                  p          1                                    &amp;lt;        x                mod                                  q          1                                    x                mod                                  p          1                                    &amp;lt;        x                mod                                  q          2                                    x                mod                                  p          1                                    &amp;lt;        x                mod                                  q          3                                    ⋮                                  x                mod                                  p          1                                    &amp;lt;        x                mod                                  q          m                                                  x                mod                                  p          2                                    &amp;lt;        x                mod                                  q          1                                    x                mod                                  p          2                                    &amp;lt;        x                mod                                  q          2                                    x                mod                                  p          2                                    &amp;lt;        x                mod                                  q          3                                    ⋮                                  x                mod                                  p          2                                    &amp;lt;        x                mod                                  q          m                                                  ⋮                                                x                mod                                  p          n                                    &amp;lt;        x                mod                                  q          1                                    x                mod                                  p          n                                    &amp;lt;        x                mod                                  q          2                                    x                mod                                  p          n                                    &amp;lt;        x                mod                                  q          3                                    ⋮                                  x                mod                                  p          n                                    &amp;lt;        x                mod                                  q          m                    where   p and   q are all different prime numbers.And if this system is solvable what is x?

Nicolas Calhoun · Accepted Answer

It seems from the question context you&#039;re using   mod to refer to the non-negative remainder on division, e.g.,   a  =  (  b  mod  c  ) means   b  =  k  c  +  a, where   k is an integer,   c is positive integer and   0  ≤  a  &amp;lt;  c. I&#039;m going to assume this. Also, if so, then note there&#039;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&#039;m also going to assume all       p    i   and all       q    i   are distinct. In that case, you can have                    (1)                    x        ≡                  y          1                        (        mod                          ∏                      i            =            1                            n                          p          i                )        ,                0        ≤                  y          1                &amp;lt;        min        (                  p          1                ,                  p          2                ,        …        ,                  p          n                ,                  q          1                −        1        ,                  q          2                −        1        ,        …        ,                  q          m                −        1        )                                (2)                    x        ≡                  y          2                        (        mod                          ∏                      i            =            1                            m                          q          i                )        ,                          y          1                &amp;lt;                  y          2                &amp;lt;        min        (                  q          1                ,                  q          2                ,        …        ,                  q          m                )            The first equation comes from that   x  ≡      y    1      (  mod        ∏          i      =      1          n        p    i    ) means   x  ≡      y    1      (  mod        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    &amp;lt;      y    2   to meet the question inequality conditions.Note although (1) and (2) don&#039;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.,                    (3)                    x        ≡        0                (        mod                          ∏                      i            =            1                            n                          p          i                )                                (4)                    x        ≡        1                (        mod                          ∏                      i            =            1                            m                          q          i                )

Solving system of modulo inequalities. Is this type of system of equations solvable? If yes, how?

Answered question

Answer & Explanation

New Questions in Algebra I