# Solving systems of linear equations over a finite ring

I want to solve equations like this (mod $2^n$):

$$\begin{array}{rcrcrcr} 3x&+&4y&+&13z&=&3&\pmod{16} \\ x&+&5y&+&3z&=&5&\pmod{16} \\ 4x&+&7y&+&11z&=&12&\pmod{16}\end{array}$$

Since we are working over a ring and not a field, Gaussian elimination doesn't work. So how can I still solve these types of equations?

-
Gaussian elimination still works for finite rings, but it has to be modified suitably. Mathematica for instance has this: LinearSolve[{{3, 4, 13}, {1, 5, 3}, {4, 7, 11}}, {3, 5, 12}, Modulus -> 16] – J. M. Dec 1 '10 at 2:18
@Qiaochu: The link you gave is for Smith normal form over a PID but the OP's ring is not a domain. – Bill Dubuque Dec 1 '10 at 2:27
@Bill: my understanding is that you can still run the algorithm over Z and then take everything mod 16 at the end. Am I wrong? Otherwise, you can fix this by adding a bunch of dummy variables and putting the system 3(x + 16p) + 4(y + 16q) + 13(z + 16r) = 3 + 16s etc. into Smith normal form over Z. – Qiaochu Yuan Dec 1 '10 at 2:54
– joriki Oct 11 '11 at 10:57

You can still use Gaussian elimination as long as you don't "divide" by things that are not relatively prime to the modulus. In this case, you can "divide" by any odd number, and perform all the usual computations. In this case, you can perform Gaussian pretty well: \begin{align*} \left(\begin{array}{ccc|c} 3 & 4 & 13 & 3\\ 1 & 5 & 3 & 5\\ 4 & 7 & 11 & 12 \end{array}\right) &\rightarrow \left(\begin{array}{ccc|c} 1 & 5 & 3 & 5\\ 3 & 4 & 13 & 3\\ 4 & 8 & 11 & 12 \end{array}\right) && \rightarrow \left(\begin{array}{ccr|c} 1 & 5 & 3 & 5\\ 0 & 5 & 4 & 4\\ 0 & 4 & -1 & 8 \end{array}\right)\\ &\rightarrow \left(\begin{array}{ccr|r} 1 & 5 & 3 & 5\\ 0 & 1 & 5 & -4\\ 0 & 4 & -1 & 8 \end{array}\right) &&\rightarrow \left(\begin{array}{ccr|r} 1 & 5 & 3 & 5\\ 0 & 1 & 5 & -4\\ 0 & 0 & 11 & 8 \end{array}\right). \end{align*} So here you get that $11z\equiv 8 \pmod{16}$. Since $11^{-1} \equiv 3\pmod{16}$, this means $z \equiv 24 \equiv 8\pmod{16}$. Then you can backsubstitute and solve. (Assuming I didn't make any mistakes with my modular arithmetic, anyway...)
If you are unlucky enough to get a congruence in which all the coefficients are even, then you can divide through by $2$ and get a congruence modulo $8$ (instead of $16$); that will lead to two solutions modulo $16$ (if you get $x\equiv 4 \pmod{8}$, that means $x\equiv 4 \pmod{16}$ or $x\equiv 8+4=12\pmod{16}$, for instance).
You basically do Gaussian elimination as usual, although you can get stuck if at some point all coefficients of a variable are, say, even. This just means that you'll have two solutions to that variable. In general, you'll pick the row in which the coefficient has the least power of $2$.