# how to solve system of congruence with multivariables [closed]

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.

-

## closed as off-topic by Yemon Choi, Willie Wong, Andrey Rekalo, Andy Putman, Karl SchwedeJun 26 '13 at 16:55

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question does not appear to be about research level mathematics within the scope defined in the help center." – Yemon Choi, Willie Wong, Andrey Rekalo, Andy Putman, Karl Schwede
If this question can be reworded to fit the rules in the help center, please edit the question.

This is not appropriate for this site. –  Karl Schwede Jun 26 '13 at 16:55

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$.