# Solve linear congruence system of equations using Gaussian Elimination

I was solving system of linear congruence equations, let me put it this way: there are n variables represented as X, the solution of X must be integers, n equations, A is the coefficient matrix, b is the is on the right hand side of =, so it looks like this:

AX = b (mod 4)

I know how to solve system of equations using Gaussian Elimination, but I was stumbled on how to apply Gaussian Elimination to solving system of linear congruence equations.

First, I turn A into row-echelon-form, but in this row-echelon-form there might be a row in which non-zero elements share common-divisor, for example, here is the last row of the row-echelon-form:

0 ... 5 | 6

According to this row, I can find out xn, that is :

(5 * xn) % 4 == 6 % 4

xn = 2

but what if the last row of the row-echelon-form looks like this:

0 ... 40 | 48

See? The non-zero of this row share common-divisor 8, and now I try to find out xn like I do above, but I can't seem to find out xn = 2, because

(40 * xn) % 4 == 48 % 4

0 == 0 # what the hell?

WHY is that? Does it mean, I have to make all the non-zero elements in the rows of row-echelon-form divided by their common-divisor before solving it?

-
I think one way to solve this is to solve it $\bmod 2$ and then use the Chinese remainder theorem to find the solution $\bmod 4$. – Henrik Finsberg Jun 3 '13 at 12:09
@HenrikFinsberg, I fail to catch up, could you plz elaborate on it ? – loganecolss Jun 3 '13 at 12:11
The reason why it fails is because $2$ does not have a multiplicative inverse $\bmod 4$ so you can't solve the system. This is because $4$ is not a prime. The Chinese remainder sais that if $N = pq$, then $A x \equiv b \bmod N$ if and only if $A x \equiv b \bmod p$ and $Ax \bmod q$. – Henrik Finsberg Jun 3 '13 at 12:23
@HenrikFinsberg, well, I still don't quite understand. – loganecolss Jun 3 '13 at 12:33
I'm sorry, but I am not sure that it works. It was just a thought. – Henrik Finsberg Jun 3 '13 at 12:51

You need to apply the general method for solving a linear modular equation. Namely,

Existence $\,\ ax\equiv b\pmod{m} \iff ax\!-\!cm = b\iff (a,m)\mid b.\,$ If so, $\ b = (a,m)e\,$
hence Bezout $\,\Rightarrow\, \exists\, j,k\!:\ aj\!-\!km = (a,m)\,\stackrel{\times\, e}\Rightarrow\,a(je) -(ke)m = (a,m)e = b.$

Uniqueness $\,\ x\,$ is unique mod $\,m/d,\, \, d = (m,a),\,$ by $\,\color{#c00}{(m/d,a/d)=1}\,$ so by Euclid's Lemma

mod $\,m\!:\ ax\equiv b\equiv ax'\Rightarrow\, m\mid a(x\!-\!a')\,\Rightarrow\,m/d\mid a/d(x\!-\!x')\,\smash[t]{\stackrel{\rm\color{#c00}{Euclid}}\Rightarrow}\, m/d\mid x\!-\!x'$

Remark $\$ You can locate lterature on thus and related elimination techniques by searching on Hermite normal form (or Smith normal form).

-
It'll take me some time to digest you answer :-), thank you very much for pointing me a way to go. But do you mean, I should use Gaussian-Elimination here ? – loganecolss Jun 3 '13 at 14:31
p.s., the equations in my post are not system of linear congruence, are they? – loganecolss Jun 3 '13 at 14:34
The elimination method is a generalization of Gaussian elimination, using the division algorithm and Bezout to take linear combinations of rows to reduce entries. Yes, the term "system of congruences" is used both cases, whether or not the moduli are equal. A web search should turn up many examples, algorithms, etc, e.g. search on "Hermite congruence system". – Key Ideas Jun 3 '13 at 14:46
I now digest some part of your answer, but still don't make sense of the Uniqueness part. And I think you're recommending me solving the system by turning the matrix into HNF, right? If so, the problem in my post will disappear? Could you please give me an example? – loganecolss Jun 4 '13 at 1:22