Solving systems of linear equations over a finite ring

Question

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](http://www.cs.umd.edu/~jkatz/THESES/bard_thesis.pdf), 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. ain't a mathematician, Dec 01 '10 at 02: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 01 '10 at 02: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 01 '10 at 02:54
See also http://math.stackexchange.com/questions/32759/number-of-solutions-to-a-set-of-homogeneous-equations-modulo-pk/32777#32777. — joriki, Oct 11 '11 at 10:57

score 8 · Accepted Answer · answered Dec 01 '10 at 02:27

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).

Basically, so long as you are careful, you can certainly do Gaussian elimination. You can even do it over more general rings, through in that case you have to other restrictions on what you can or cannot conclude.

Hi, in this case, how do we know if this equation system actually have exact one solution of more than one solution? In typical case in $\mathbb{R}$ without Ring involved, we check if the $\det(A) = 0$. Now in the case involved modular ring, is it still only check if $\det(A) = 0$? — zbo, Apr 10 '23 at 03:36
@zbo You need the determinant to be relatively prime to the modulus, so that the matrix is invertible. — Arturo Magidin, Apr 10 '23 at 03:48
In the other side, if the determinant of $A$ is not relatively prime to the modulus $N$, will $Ax=b \mod N $ definitely have more than one solution? — zbo, Apr 14 '23 at 09:09

score 3 · Answer 2 · answered Dec 01 '10 at 02:23

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$.

Solving systems of linear equations over a finite ring

2 Answers2