I'm aware for coprime moduli we have the CRT for solving the problem

$$ \begin{matrix} a_0 x \equiv b_0 \mod m_0 \\ a_1 x \equiv b_1 \mod m_1 \\ \vdots \\ a_n x \equiv b_n \mod m_n \end{matrix} $$

And if we relax the "coprime" condition, we still have a general technique of substitution, at our disposal.

But now i'm curious, what about the general problem of finding classes of $x_0 ... x_k$ such that:

$$ \begin{matrix} a_{00}x_0 + a_{01} x_1 + ... a_{0k} x_k \equiv b_0 \mod m_0 \\ a_{10} x_0 + a_{11} x_1 + ... a_{1k} x_k \equiv b_1 \mod m_1 \\ \vdots \\ a_{n0} x_0+ a_{n1} x_1 + ... a_{nk} x_k \equiv b_n \mod m_n \end{matrix} $$

Does there exist a general algorithm for this, akin to substitution from earlier?


1 Answer 1


Sure, the keyword is "multivariable Chinese remainder theorem." A nice exposition can be found here. The general theorem states that if all mods $m_i$ are relatively prime and each row $i$ has an $a_{ij}$ that is relatively prime to $m_i$, then there's going to be at least one solution. The mechanical way of solving the system can be done by row reduction, except in a few special cases. The idea is pretty straightforward: reduce each system to a problem that can be solved by CRT.


You must log in to answer this question.

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