title: Algorithm for linear equations with more solutions
body: <p>Can someone help me out with algorithm for solving linear equations in modular arithmetic (!). I need only the "smallest" solution. Smallest means lexicographically first.</p>
  
  <p>Let's have this system: <br />
  3x1+2x2=3<br/>
  4x1+3x2+1x3+2x4=4<br/>
  Number next to x is index.</p>
  
  <p>Matrix for this system where we use modulo 5 (0&lt;=x&lt;=p  where p is our modulo) is <br/>
  3 2 0 0 0 | 3 <br />
  4 3 1 2 0 | 4</p>
  
  <p>The smallest solution for this is (0,4,0,1,0). I have to write an algorithm which will give me that solution. 
  I was thinking about brute-force, because p&lt;1000. But I dont how to do it, because in this situation in first row I have to x1=0 ... p-1 , then solve x2, in the second row i have to pick x3= 0 ... p-1. And solve x4. I have to do this until that system of equations hold. If I go from 0 .. p-1, then the first solution I get will be the smallest one.</p>
  
  <p>PS:There can a lot of forms of matrix, like:<br/>
  3 2 4 0 0 | 3 <br />
  4 3 1 2 1 | 4</p>
  
  <p><br/>
  1 2 0 0 0 | 3 <br />
  3 0 3 0 0 | 3 <br />
  4 3 1 2 3 | 4 <br />
  etc.</p>
  
  <p>Sorry for my english, I am from asia.</p>
  
  <p>Edit: I was thinking about how to determine which variables are parameters. But can't figure it out....</p>