How to solve system of linear congruences with the same modulo?

Question

I have to write program which is solving linear congruences withe the same modulo. I have system of congruences like that(only 2 unknowns x and y): $$\begin{cases} a_1x+b_1y \equiv c_1\pmod n \\ a_2x+b_2y \equiv c_2\pmod n \\ \end{cases} $$

I'm using Cramer's rule now and it works when the modulus is prime, but when modulus is not prime, my program behaves incorrectly.

Answer 1

This is not as simple as it may look. For example, there may be multiple solutions for even a single equation ($2x\equiv 0 \pmod 4$ has 2 solutions$\pmod 4$, for example). This breaks the nice theory one knows from the reals. That it works for primes $p$ is due to the fact that the the numbers you are working with also form a field, just like the reals.

It seems you have to go the hard way and

1. factor $n$ into prime powers: $n=p_1^{\alpha_1}p_2^{\alpha_2}\ldots$,
2. you need to solve the problem independently for each prime power $p_i^{\alpha_i}$ (see next steps) and at the end combine the results using the Chineese reminder theorem.
3. for each prime power $p_i^{\alpha_i}$, first solve it$\pmod {p_i}$. This will work with what you have it seems. This gives you for all variables either a result$\pmod {p_i}$ or no information (if the coefficinet before the variable was a multiple of $p_i$ in all equations). Introduce new variables ($x_i'$) for the ones you got results for ($x_i$) in the form of $x_i=p_ix_i' + r_i$.
4. reformulate your equations using the new $x_i'$ variables and the older ones that did not yield information in step 3. You will see that now all coefficients before variables contain the factor $p_i$. Now it's time to consider$\pmod {p_i^2}$
5. You can divide all your equations by $p_i$. If the constant term is not divisible by $p_i$, the system has no solution. You must also divide the modulus by $p_i$, this is an equivalent operation! ($pa\equiv pb \pmod {p^2}$ means the same as $a\equiv b \pmod {p}$.
6. Now you are back where you started, you can solve the system with (possibly) some new variables $\pmod {p}$ and continue as in steps 3-5. Each time you get information about your variables modulo a higer power of $p_i$, and at the end you get them for what you need, $\pmod {p_i^{\alpha_i}}$

Again, this is probably at least a few days work, not a few hours. Maybe somebody else has a better idea, though.