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

  • $\begingroup$ Where are you running into trouble? $\endgroup$
    – user14972
    Oct 13 '12 at 2:26
  • $\begingroup$ @Hurkyl I'm not sure that it's okay to solve n x m equations. $\endgroup$
    – 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.

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

  • $\begingroup$ um.. is there more faster solution than just substracting? $\endgroup$
    – Love Paper
    Oct 13 '12 at 5:05
  • $\begingroup$ 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. $\endgroup$
    – adam W
    Oct 13 '12 at 5:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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