Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

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. :)

share|cite|improve this question
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
up vote 1 down vote accepted

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.

It is the same idea, just combine the rows until things are simplified.

share|cite|improve this answer
um.. is there more faster solution than just substracting? – Love Paper Oct 13 '12 at 5:05
Not generally. The computation count grows quickly respective to number of variables. Doing anything by hand calculation is not recommended for more than 3 variables, maybe 4 if you have multiple pages of paper and much patience. – adam W Oct 13 '12 at 5:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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