# How can I use Gauss elimination to solve equations with Modular arithmetics?

I've given some equations look like this.

$a_{1,1} x_1 + a_{1,2} x_2 + a_{1,3} x_3 + ... + a_{1,n} x_n\equiv 1 \mod p$

$a_{2,1} x_1 + a_{2,2} x_2 + a_{2,3} x_3 + ... + a_{2,n} x_n\equiv 1\mod p$

$...$

$a_{m,1} x_1 + a_{m,2} x_2 + a_{m,3} x_3 + ... + a_{m,n} x_n\equiv 1\mod p$

($p$ is prime, I know the values of $a_{1..m, 1..n}$, I have to get $x_{1..n}$) (all of the values of $a_{1..m, 1..n}, x_{1..n}$ should not be negative, and they must be integers)

I think I can solve this using Gaussian elimination, but I'm not sure how to use this.

I appreciate any help or tip. Thank you in advance. :)

-
Where are you running into trouble? – Hurkyl Oct 13 '12 at 2:26
@Hurkyl I'm not sure that it's okay to solve n x m equations. – Love Paper Oct 13 '12 at 2:28

If you are familiar with Gaussian elimination, then you can do this just as easily, all the same operations are valid, just reduce $\mod{p}$ any time you desire to simplify by reducing number size. If it is the fractions that you are worried about, then do only integer operations. For example, if you have numbers 2 and 5, first subtract 2*2 from 5 to get 1. The larger numbers may not get to 1 so fast, but the idea is the same. Subtract integer amounts that reduce the numbers, and repeat with the smaller numbers until all is reduced.