# Gaussian elimination mod k

We have this assignment in programming class, but I believe posting it in math will make more sense.

So we're supposed to write a program that takes $n$ equations with each $n$ coefficients, $n\leq10$, as well as 'a value for mod' and then solves the whole thing. Coefficients are supposed to be in $\mathbb{Z}_p^*$, but I don't really know what that is.

Now I have two things I'm not sure about:

• how exactly is that with the mod supposed to work? I never saw something like that before, just common Gauss elimination. I also heard it only makes sense when the mod value is prime. So how to handle a non-prime mod value?

• if I have less than $n$ equations left, how could I determine how many solutions the system has?

Thank you for any help.

Edit: to help my understanding of how the process works:

Let's say I have $1x+2y=3 \mod5$ and $2x+3y=4\mod 5$. The result is supposed to be $(4,2)$.

Also, for $1x+2y=4 \mod4$ and $3x+4y=5 \mod4$ the prof's example program crashes. What is going on there that he missed to pay attention to?

-
If I understand correctly you are supposed to program the solution of an $n\times n$ system in $\mathbf Z/k\mathbf Z$, where $n$ and $k$ are given on input. If $k$ is prime, all you need in addition to the usual Gaussian elimination ingredients is a routine to compute inverses modulo $k$. If it is not prime, you could do the same (the routine is not much different), but the inverse might not exist, even for values not divisible by $k$; this means that Gaussian elimination may get blocked. – Marc van Leeuwen Nov 18 '12 at 9:47
You can also use all the "usual" arithmetic operations you usually use in $\,\Bbb Q\,$ except multiplication by $\,1/k\,$ , when working $\,\pmod k\,$ – DonAntonio Nov 18 '12 at 11:18
@Don, it's not safe to multiply by $1/d$ for any $d$ with $\gcd(d,k)\gt1$. – Gerry Myerson Nov 18 '12 at 11:32
Good point, @GerryMyerson . I was assuming $\,k\,$ is a prime. Than k – DonAntonio Nov 18 '12 at 11:42
@MarcvanLeeuwen It would be $n\times n+1$ i think, since each equation also has $n+1$ elements (n coefficients and an answer). Thanks for that. keyword to compute inverses mod k is extended euclidian algorithm, right? – foaly Nov 19 '12 at 4:57