Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
4  
4  
@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
    
See also math.stackexchange.com/questions/32759/…. –  joriki Oct 11 '11 at 10:57
add comment

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.