Solving a linear system of congruences in general

This solver solves for \(x\) all systems of congruences

\[\begin{aligned} a_1x&\equiv b_1 \pmod{m_1}\\ &\vdots\\ a_nx&\equiv b_n \pmod{m_n} \end{aligned}\]

for \( n\in\mathbb{N}, a_i,b_i,m_i\in \mathbb{Z}, m_i\neq 0\). If there is a solution, it will be a congruence \(x=S \pmod{M}\), which the solver will return. If there is no solution, the solver will report which congruences are unsolvable or pairwise irreconcilable.

How the solver works

The solver first attempts to solve each congruence \(ax\equiv b \pmod{m}\) individually. Let \(d=\gcd(a,m)\). If \(d \nmid b\), the congruence has no solutions and hence the whole system has no solutions. Otherwise, let \(a'=a/d\), \(b'=b/d\) and \(m'=m/d\). Now, using extended Euclidean division to find \(u,v\in \mathbb{Z}\) such that \(a'u+m'v=1\), the solutions \(x\) are exactly those integers satisfying

\[ x \equiv ub' \pmod{m'}\text{.} \]

Suppose then that all congruences can be individually solved in the form \(x\equiv c \pmod{m'}\). Consider a pair of congruences \(x\equiv c_i \pmod{m'_i}\) and \(x\equiv c_j \pmod{m'_j}\) and let \(g=\gcd(m'_i,m'_j)\). If \(c_i \not\equiv c_j \pmod{g}\), the pair has no joint solution and is said to be irreconcilable. Otherwise, let \(m^\ast_i=m'_i/g\), \(m^\ast_j=m'_j/g\), and use extended Euclidean division to find \(p,q\in \mathbb{Z}\) satisfying \(m_i^\ast p + m_j^\ast q = 1\). Then let \(e=c_im_j^\ast q + c_jm_i^\ast p\) and \(\ell=\operatorname{lcm}(m'_i,m'_j)\). The solutions to the pair are then exactly those integers \(x\) of the form

\[ x\equiv e \pmod{\ell}\text{.} \]

In general, the system of congruences \(x\equiv c_i \pmod{m'_i}\) has a solution if and only if all congruences are pairwise reconcilable. If so, then the overall solution may be obtained by iterating the process for pairs on successive elements. We can treat systems of \(1\) or \(0\) congruences without special cases by folding this process starting from the identity congruence \(x\equiv 0 \pmod{1}\). This method is known as the generalised Chinese remainder theorem.

The solver normalises all congruences \(x=c \pmod{m}\) so that \(m\geq 1\) and \(0\leq c < m\).