A Special System of Linear Congruences

[e(ho0n3]

Suppose I have a system of m equations in k unknowns

<br /> \begin{align*}<br /> a_{11}x_1 + a_{12}x_2 + \cdots + a_{1k}x_k &amp;= 0 \pmod d \\<br /> &amp;\vdots \\<br /> a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mk}x_k &amp;= 0 \pmod d<br /> \end{align*}<br />

with the restriction that 0 \le x_n &lt; n. How do I solve such a thing? Will Gaussian elimination work? What if I get a solution where one of the x's is outside its bounds?

 

[JSuarez]

Gaussian elimination will work, if all operations are done mod d (I suspect this d should be n).

What if I get a solution where one of the x's is outside its bounds?

Reduce it mod d (or n).

 

[e(ho0n3]

Gaussian elimination will work, if all operations are done mod d (I suspect this d should be n).

No, it should be mod d.

What if I get a solution where one of the x's is outside its bounds?

Reduce it mod d (or n).

I messed up with the restrictions. It should be 0 \le x_n \le i_n for some given i_n. If I mod an x by d or by i_n, it will screw up the solution because when I plug a mod'ed x back into the system, the numbers won't come out right. I would have to mod all the x's by d, by this will automatically happen if I do Gaussian elimination by mod d. However, the problem remains: What if one of the x's is outside its bound?

 

[JSuarez]

Then, if after reducing mod d, there is a violation of any of the restrictions, we must conclude that there is no solution.

 

[e(ho0n3]

You have a good point there. Thanks for your help.