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

Holetaug 2022-07-10 Answered
Solving system of modulo inequalities. Is this type of system of equations solvable? If yes, how?
x mod p 1 < x mod q 1 x mod p 1 < x mod q 2 x mod p 1 < x mod q 3 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 x mod p 2 < x mod q m x mod p n < x mod q 1 x mod p n < x mod q 2 x mod p n < x mod q 3 x mod p n < x mod q m
where p and q are all different prime numbers.
And if this system is solvable what is x?
You can still ask an expert for help

Want to know more about Inequalities systems and graphs?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Nicolas Calhoun
Answered 2022-07-11 Author has 15 answers
It seems from the question context you'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 < 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
(1) x y 1 ( mod i = 1 n p i ) , 0 y 1 < 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 < y 2 < 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 < 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.,
(3) x 0 ( mod i = 1 n p i )
(4) x 1 ( mod i = 1 m q i )
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-03-07

Graph the feasible region for the system of inequalities
y>4x1
y2x+3

asked 2022-06-03
The given question is :
Consider the sets defined by the real solutions of the inequalities
A = { ( x , y ) : x 2 + y 4 1 } B = { ( x , y ) : x 4 + y 6 1 }
A. B A
B. A B
C. Each of the sets A B, B A and A B is non-empty
D. None of the above
how to solve this without using any such plotter?
asked 2022-06-23
Consider a linear optimization program like the following
max i = 1 T x i T s.t. a x i + b x i + 1 1 , i 1 , x i 0
Assume that we take T . Say that a > 0 , b > 0 and hence the constraints make sure we have some nice properties like x i have to be in some bounded region.
There is a lot of structure in this problem and its almost 'symmetric' if we shift every index by 1. I wonder if something can be said about the solution. For example x i = c   i. Does this hold for more general linear inequalities that are almost shift-invariant?
There are some similarities to this problem with MDPs and in particular it resembles an Average reward maximization problem. However nothing is random in this problem
asked 2022-05-21
I have to graphically represent the following subset in the complex plane being z a complex number: A = 1 < | z | < 2
What I did previously was solve it like it was a regular inequality system in the real numbers, resulting in b < a + 4 and b > a + 1
How can I solve this?
asked 2022-06-09
Solve a system of three inequalities in three unknowns
(1) X > 1
(2) Y < Z ( 1 + X )
(3) Z < 1 Y X
asked 2022-07-28
Concentric with thw circle x 2 + y 2 + 8 x 3 y + 16 = 0 and touching the line 4x+3y=12
asked 2022-06-05
Suppose that we are given a subroutine which, given a system of linear inequalities A x b, x R n , either produces a solution or decides that no solution exists.
Construct an algorithm that uses a single call of this subroutine and which returns an optimal solution (if it exists) to the following linear programming problem:
minimize  c T x subject to:  A x = b x 0
Well, I think I should take a look at the dual problem.
The dual is:
maximize  p T b subject to:  A T p   c
Then I would call the subroutine for the matrix A T and to the vector c to find a dual feasible point y.
I tried to use complementary slackness to construct a primal solution and to decide if y is optimal but it didn't work .