There `n` variables **x1,x2,...,xn** represented as **X**, `n` equations whose coefficient matrix (n\*n) is represented as **A**, and this system looks like this:


**AX = B (mod k)**


Initially I was trying to solve this system using ordinary **Gaussian Elimination**, can't seem to get right solution.


Can't I just apply ordinary **Gaussian Elimination** here on system of congruence? What is the right way to solve it?


Any suggestion is highly appreciated.



how to solve system of congruence with multivariables
If $k$ is a prime number, Gaussian Elimination in the finite field $F\_k$ works as usual.


In other cases, one considers $A$ as a matrix with integral coefficients. You put it in Smith normal form : that is $A$ is equivalent to a matrix $A'$, with $A'$ having only diagonal coefficients $(d\_1,d\_2,\dots,d\_n)$ with $d\_i$ dividing $d\_{i+1}$.


Write $A = PA'Q$ with $P,Q$ invertible and computable. Your system is just $A'(QX) = P^{-1}B$ (mod $k$) because for an invertible $P$ and $C$ a column vector, $C$ has coefficients divisible by $k$ if and only if $PC$ has coefficients divisible by $k$. In this way, you find immediately the eventual solution $QX$, hence $X$.


You can also use Hermite normal form.


