1. ## equations involving modulo

Hi,
I need help on solving equation system witch involves modulo.
My equation looks like this:
a11x1+a12x2+a13 mod 10 = a14
a21x1+a22x2+a23 mod 10 = a24

It would be pretty simple if there where no mod operation, but now i've no idea how to solve it.

2. You can always just solve it as you would without the modulo, then transfer your answers into modulo notation (e.g. 1/3 = 7 mod 10 because 7*3=1 mod 10).

Or, you can try and use the modulo at the same time.

For example, I have the following two equations. They have solutions x=11, y=12 (so mod 10 x=1 and y=2),

$2x-y=9$,
$x+y-9=15$.

These become,

$2x-y=-1\text{ mod }10$,
$x+y+1=5\text{ mod }10 \Rightarrow x+y=4 \text{ mod }10$.

$3x=3 \text{ mod }10$.

We now have the question what is $x$'? In this case, it is obviously 1. However, it won't always be so simple. For example, if 3x=8 mod 10, how would you proceed?

Well, 3*7=21=1 mod 10, so we have found the multiplicative inverse of 3 mod 10. Therefore, 3*(7*8)=8 mod 10. 7*8=56=6 mod 10. Therefore, 3*6=8 mod 10, and so x=6. This is the standard' way of solving for such an x. You find the z such that az=1 mod n, and then you have a*(zm)=m mod n.

Anyway, I deviate. We have x=1 and the two equations,

$2x-y=-1\text{ mod }10$,
$x+y=4 \text{ mod }10$.

Substituting into the second equation, we have y=3, as required.

Does that help?

I understand that these equations are pretty simple, have many solutions and it's easy to solve them manualy.
Like in your example x=11 and y=23 works too.

But i'm trying to write a computer code to solve these equations amd manual method doesn't work here.

Some how i need to get rid of modulo operation
transform my equations from this form:
a11x1+a12x2+a13 = a14 mod 10
a21x1+a22x2+a23 = a24 mod 10

to:
a11x1+a12x2+a13 = a14 + 10*q1
a21x1+a22x2+a23 = a24 + 10*q2

For the first equation i just could choose random quotient and eliminate mod operation, but i'm not sure what to do with second.

4. Originally Posted by spak
I understand that these equations are pretty simple, have many solutions and it's easy to solve them manualy.
Like in your example x=11 and y=23 works too.

But i'm trying to write a computer code to solve these equations amd manual method doesn't work here.

Some how i need to get rid of modulo operation
transform my equations from this form:
a11x1+a12x2+a13 = a14 mod 10
a21x1+a22x2+a23 = a24 mod 10

to:
a11x1+a12x2+a13 = a14 + 10*q1
a21x1+a22x2+a23 = a24 + 10*q2

For the first equation i just could choose random quotient and eliminate mod operation, but i'm not sure what to do with second.
No, you want keep the modulo. You can use the Euclidean algorithm to solve the equation $ax=b \text{ mod } n$ as follows,

By the E.A. $gcd(a, n) = ap+nq$. It must be that $gcd(a, n) \mid b$, otherwise your equation has no solutions. Therefore, $x=pr \text{ mod }n$ where $gcd(a, n) = br$ (by multiplying $gcd(a, n) = ap+nq$ through by r and then applying mod n).