Can someone explain me how to solve linear equation system in modular aritmetic when i have less equations than variables. I need algorithm for this, something with gaussian matrix maybe.
$$4x_1 – 2x_2 + 0x_3 = 2$$
$$-x_3 + 4x_4=1$$
Where everything is in modulo = 3
Matrice for this system is
$ \left( \begin{array}{ccc}
1 & 1 & 0 & 0 & 2 \\
0 & 0 & 2 & 1 & 1 \\
\end{array} \right)$ i think.
I need only a "smallest"solution. In this case it is $(0,2,0,1)$.
I know that there are 9 solutions for this system.Thanks
Best Answer
If you are working only over fields $\rm\:\Bbb Z/p,\:$ for prime $\rm\:p,\:$ then Gaussian elimination works fine (as it does over any field). For more general coefficient rings there are various generalizations, such as Hermite and Smith normal form algorithms.