Chinese remainder theorem

If \(m_1,\dots,m_k\) are pairwise coprime, the system \(x\equiv a_i \pmod{m_i}\) has a solution, and every other solution is congruent to it modulo \(M=m_1\cdots m_k\). The proof builds the solution with \(M_i=M/m_i\) and an inverse \(y_i\) of \(M_i\) modulo \(m_i\), giving \(x=\sum a_i M_i y_i\). The inverse exists because \(\gcd(M_i,m_i)=1\), which follows from coprimality.

To solve \(x\equiv 2 \pmod 3\) and \(x\equiv 3 \pmod 5\), take \(M=15\). With \(M_1=5\), the inverse of \(5\) modulo \(3\) is \(2\), and with \(M_2=3\), the inverse of \(3\) modulo \(5\) is \(2\). Thus \(x\equiv 2\cdot5\cdot2+3\cdot3\cdot2=38\equiv 8 \pmod{15}\), which checks out by dividing \(8\) by \(3\) and by \(5\).

A typical mistake is applying the theorem to moduli that are not coprime, such as \(x\equiv 0 \pmod 4\) and \(x\equiv 1 \pmod 6\), where there is no solution because \(x\) would have to be both even and odd. Before using the theorem, check that \(\gcd(m_i,m_j)=1\) for every pair of moduli.