Allow a system of coupled equations with a different module

Question

Is there any algorithm for solving a system of equations expressed in different moduli spaces? For example, consider this system of equations:

(x1 + x2 ) % 2 = 0 ( x2 + x3) % 2 = 0 (x1 + x2 + x3) % 3 = 2 

One solution to this system:

 x1 = 0 x2 = 2 x3 = 0 

How could I arithmetically find this solution (without using brute force algorithm)?

thanks

Answer 1

You can rewrite these equations as

 x1 + x2 = 2*n1 x2 + x3 = 2*n2 x1 + x2 + x3 = 3*n3 + 2 

Now this is the problem of the linear Diophantine equation, for which there are solutions in the literature.

Example: http://www.wikihow.com/Solve-a-Linear-Diophantine-Equation

Also see: https://www.math.uwaterloo.ca/~wgilbert/Research/GilbertPathria.pdf

Algorithm:

Write xi as a nks function

In this case:

 x3 = 3*n3 + 2 - 2*n1 x2 = 2*n2 - (3*n3 + 2 - 2*n1) x1 = 2*n1 - (2*n2 - (3*n3 + 2 - 2*n1)) 

Since there is no division on the right side, select any (n1, n2, n3) and you should get a solution.

Answer 2

The first line is the same as x1, x2 - all even or all odd numbers. The second line is the same as x2, x3 - all even or all odd numbers. Therefore, x1, x2, x3 are all even or all odd numbers. From the third line we can replace the question with "3 odd or 3 even numbers that accumulate up to 3k + 2".

Answer 3

You can convert your system to modular LCM (smallest total). Just find the LCM of the whole equation modulo and multiply each equation accordingly.