How do you solve a system of linear equations in modulus arithmetic?

Question

Say you have a system if equations of the form:

$ax+by \equiv z \mod(n)$

$cx + dy \equiv w \mod(n)$

Where the only unkown values are x and y

What is the approach to solve a system like this?

Answer 1

For a 2 by 2, just use Cramer's rule:

https://en.wikipedia.org/wiki/Cramer%27s_rule

Answer 2

If you solve it regularly you get $y = \frac {aw - cz}{da-cb}$ and $x = \frac {zd - bw}{da-cb}$.

The only issue is if $\frac 1{da-cb}$ will be expressible modulo $n$.

Reduce these fractions to lowest terms: Let's say $x = \frac {zd-bw}{da-cb} = \frac AB$.

Then we need to solve $Bx \equiv A \mod n$. That will have a solution if and only if $\gcd(B,n) = 1$. If $\gcd(B, n) > 1$ then for $B\equiv A \mod n$ (i.e. if $A = mn + B$ then $\gcd(n,B)|A$ which is a contradiction to them being in lowest terms.

And if $\gcd(B, n) =1$ then you can solve $jB + kn = 1$. So solve for $j*B \equiv 1 \mod n$. We can call that $\frac 1B \equiv j \mod n$.

This does not mean that $j = kn + \frac 1B$ for some integer $n$ but is does mean that $jB \equiv 1 \mod n$.

Thus $x \equiv \frac AB \equiv jA \mod n$ will be the solution.

....

It may be easier to see this with an example $2x + 3y = 3$ and $2x - 3y = -1$ mean that $x = \frac 12$ and $y = \frac 23$.

We want to solve $2x + 3y \equiv 3 \mod 5$ and $2x - 3y \equiv -1 \equiv 4 \mod 5$.

So we must find value for $\frac 12 \mod 5$. i.e a solution to $2x \equiv 1 \mod 5$. That is ... $3$. So $x \equiv 3 \mod 5$.

And we must find a value for $\frac 13 \mod 5$.i.e. a solution to $3x\equiv 1 \mod 5$. Well that is $2$. So $y \equiv \frac 23 \equiv 2*2 \equvi 4 \mod 5$

And does that work? $2*3 + 3*4 \equiv 18\equiv 3 \mod 5$. And $2*3 - 3*4 \equiv -6 \equiv 4 \mod 5$.

Yup, it works.

===

An example that wouldn't work is $2x + 3y \equiv 3 \mod 6$ and $2x - 3y \equiv -1 \equiv 5 \mod 6$.

We'd need to solve $\frac 12 \equiv \mod 6$ i.e. a solution to $2x \equiv 1 \mod 6$ and there is no such answer. Likewise there is no solution to $3x \equiv 1 \mod 6$. So there is no solution.

Which makes sense.

Conside $2x + 3y \equiv 3 \mod 6$. If $y$ is odd then $x$ must be a multiple of $3$. If $y$ is even then $2x \equiv 3\mod 6$. That's impossible. $2x - 3$ must be a multiple of $6$ so $x$ must be a multiple of $3$ but that makes $2x\equiv 0 \mod 6$.

So the only solution is $y$ is odd and $x$ is a multiple of $3$.

But $2x -3y = 2(3k) - 3(2j + 1) \equiv 3\mod 6 \not \equiv -1 \mod 6$.