- #1

- 1,357

- 0

## Main Question or Discussion Point

Suppose I have a system of m equations in k unknowns

[tex]

\begin{align*}

a_{11}x_1 + a_{12}x_2 + \cdots + a_{1k}x_k &= 0 \pmod d \\

&\vdots \\

a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mk}x_k &= 0 \pmod d

\end{align*}

[/tex]

with the restriction that [itex]0 \le x_n < n[/itex]. 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?

[tex]

\begin{align*}

a_{11}x_1 + a_{12}x_2 + \cdots + a_{1k}x_k &= 0 \pmod d \\

&\vdots \\

a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mk}x_k &= 0 \pmod d

\end{align*}

[/tex]

with the restriction that [itex]0 \le x_n < n[/itex]. 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?