-1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is not appropriate for this site. $\endgroup$ Jun 26, 2013 at 16:55

1 Answer 1

0
$\begingroup$

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.

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

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