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

Burress

Interesting problem. Certainly the decision procedure for Presburger arithmetic would be work, but it's complicated and slow. The interesting case is when the moduli are powers of the same prime; given an equation ... = ... mod (p q) where gcd(p, q) = 1, we can split it as ... = ... mod p and ... = ... mod q, then assemble the final solution using the Chinese Remainder Theorem. – Grappa

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.

Leeuwenhoek

Well is there an algorithm to automatically solve a system of Diophantine equations like this one, I didn't find any... – Burress

Thanks for the answer. Using matrix unimodular raw reduction method, I was able to automatically express xi as functions of nis. But I basically end up with a system with m unknown ni variables now (instead of m xi unknown variables), and I don't really understand how my algorithm can automatically choose the correct ni values (in the example there is no division so each ni is free. But would it always be the case, can't I end up with constraints on that ni?) – Burress

@ThomasBernard I am not an expert on this subject. You should probably read the paper I linked. In any case, the general case is not trivial. – Leeuwenhoek

Yes I read the paper. Indeed the general case is far from trivial: arxiv.org/pdf/1206.5114v1.pdf. As for my use case, in case of multiple solutions, I also have to find the one for which Sum{abs(xi)} is minimal, the method of the paper didn't suit my needs. I finally end-up with an hybrid solution of matrix reduction and brute force solutions space search that satisfy me (runs in less than a second with hundred of variables on my desktop). Thanks for your help – Burress

Coming to this a mere 7+ years late...A common way to solve such a problem uses the Hermite Normal Form is a way similar to what one would do using Gaussian elimination to find rational solutions in the absence of moduli. – Antebi

Answer 2

First line is same as saying x1, x2 is all even or all odd numbers. Second line is same as saying x2, x3 is all even or all odd numbers. Hence x1,x2,x3 is all even or all odd numbers. From third line we can replace the question to "3 odd or 3 even numbers that accumulate to 3k+2."

Steck

Answer 3

You can convert your system to modulo LCM (least common multiple). Just find the LCM of all equation's modulo, and multiply each equation appropriately.

Haversack

Thanks for your answer. Could you develop it a bit more? When you say "multiply each equation appropriately", what does it mean exactly? In the example I posted the LCM is 6, so what would be the system converted to modulo 6? – Burress

@ThomasBernard yes, exactly. First 2 should be multiplied by 3, the last - by 2. – Haversack

Thanks. However I now end up with an other problem. To solve my system of linear equations modulo n, I used to use a Gauss-Jordan elimination algorithm that require to multiply some lines by their invert modulo to get only "1" values on the diagonal of the row echelon matrix matrix. However, here it is impossible as 2^-1 mod 6 and 3^-1 mod 6 doesn't exist... (and I only have 2, 3 and 0 values in my matrix) – Burress