6
$\begingroup$

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

  • 0
    @Hurkyl I'm not sure that it's okay to solve n x m equations.2012-10-13

1 Answers 1

1

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.

  • 0
    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.2012-10-13