9
$\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?

  • 1
    [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]`2010-12-01
  • 5
    http://en.wikipedia.org/wiki/Smith_normal_form2010-12-01
  • 4
    @Qiaochu: The link you gave is for Smith normal form over a PID but the OP's ring is not a domain.2010-12-01
  • 0
    @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.2010-12-01
  • 0
    See also http://math.stackexchange.com/questions/32759/number-of-solutions-to-a-set-of-homogeneous-equations-modulo-pk/32777#32777.2011-10-11

2 Answers 2

7

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.

2

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