MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

closed as off-topic by Yemon Choi, Willie Wong, Andrey Rekalo, Andy Putman, Karl Schwede Jun 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
up vote 0 down vote accepted

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.

share|cite|improve this answer
Why should k be prime? What if it's not? Could you please show me some concrete examples? – Ecolss Jun 6 '13 at 2:40
Smith and Hermite normal forms work over the integers. You can find a lot of examples by googling it. – Jeremy Daniel Jun 6 '13 at 5:33
Thanks, I'm just having a time figuring out why Gaussian Elimination works only when k is prime. – Ecolss Jun 6 '13 at 13:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.