Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
This is not appropriate for this site. –  Karl Schwede Jun 26 '13 at 16:55
add comment

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.

1 Answer

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|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
add comment

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