# Linear equation system in modular aritmetic

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

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.

• I still don't get how to get that "smallest"solution from that matrice :/ – JoshuaM Mar 20 '13 at 17:39
• @JoshuaM You only now mentioned that you needed only a "smallest" solution. My answer is to your original question - which gave no hint of that constraint. – Math Gems Mar 20 '13 at 17:43
• Yea I know, and can you help me with the "smallest"solution ?:) – JoshuaM Mar 20 '13 at 17:47
• @JoshuaM For the minimization problem you might find some techniques of interest by searching on "frobenius problem linear programming". – Math Gems Mar 21 '13 at 3:33

Everything's modulo $\,3\,$ :

$$4x_1-2x_2=2\iff x_1+x_2=2\iff x_2=2+2x_1$$

$$-x_3+x_4=1\iff 2x_3+x_4=1\iff x_4=1+x_3$$

So the general solution has the form

$$\left\{\,\begin{pmatrix}x_2\\2+2x_1\\x_3\\1+x_3\end{pmatrix}\;;\;\;x_1\,,\,x_3\in\Bbb F\right\}$$

Where $\,\Bbb F\,$ is the algebraic structure from where the variables are taken (seemingly, field with characteristic $\,3\,$)

• Can you explain me how to make algorithm for that? If I am given less equation than variables? I need only the smallest solution. In this case it is (0,2,0,1) – JoshuaM Mar 20 '13 at 16:39
• I'm not sure how "smallest" and "biggest" orwhatever work in field with positive characteristic...anyway, the above is just ismple linear algebra appleid to a field of char. $\,3\,$ ... – DonAntonio Mar 20 '13 at 18:08