I was solving system of linear congruence equations, let me put it this way: there are
n variables represented as X, the solution of X must be integers,
n equations, A is the coefficient matrix, b is the is on the right hand side of =, so it looks like this:
AX = b (mod 4)
I know how to solve system of equations using Gaussian Elimination, but I was stumbled on how to apply Gaussian Elimination to solving system of linear congruence equations.
First, I turn A into row-echelon-form, but in this row-echelon-form there might be a row in which non-zero elements share common-divisor, for example, here is the last row of the row-echelon-form:
0 ... 5 | 6
According to this row, I can find out xn, that is :
(5 * xn) % 4 == 6 % 4
xn = 2
but what if the last row of the row-echelon-form looks like this:
0 ... 40 | 48
See? The non-zero of this row share common-divisor 8, and now I try to find out xn like I do above, but I can't seem to find out xn = 2, because
(40 * xn) % 4 == 48 % 4
0 == 0 # what the hell?
WHY is that? Does it mean, I have to make all the non-zero elements in the rows of row-echelon-form divided by their common-divisor before solving it?