11
$\begingroup$

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?

$\endgroup$
5
  • 2
    $\begingroup$ 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] $\endgroup$ Commented Dec 1, 2010 at 2:18
  • 5
    $\begingroup$ en.wikipedia.org/wiki/Smith_normal_form $\endgroup$ Commented Dec 1, 2010 at 2:20
  • 4
    $\begingroup$ @Qiaochu: The link you gave is for Smith normal form over a PID but the OP's ring is not a domain. $\endgroup$ Commented Dec 1, 2010 at 2:27
  • 1
    $\begingroup$ @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. $\endgroup$ Commented Dec 1, 2010 at 2:54
  • $\begingroup$ See also math.stackexchange.com/questions/32759/…. $\endgroup$
    – joriki
    Commented Oct 11, 2011 at 10:57

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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$? $\endgroup$
    – zbo
    Commented Apr 10, 2023 at 3:36
  • 1
    $\begingroup$ @zbo You need the determinant to be relatively prime to the modulus, so that the matrix is invertible. $\endgroup$ Commented Apr 10, 2023 at 3:48
  • $\begingroup$ 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? $\endgroup$
    – zbo
    Commented Apr 14, 2023 at 9:09
3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .