resolve a system of linked equations with different modulo

Question

Is there any algorithm to solve a system of equations expressed in different modulo spaces? For exemple, consider this system of equations:

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

One of the solutions of this system is:

x1 = 0
x2 = 2
x3 = 0

How could I arithmetically find this solution (without using a 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 a linear Diophantine equation problem 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 function of nks

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-hand side, pick any (n1, n2, n3) and you should get a solution.