Solving Systems of Congruences: The Chinese Remainder Theorem

A number leaves a remainder of \(2\) when divided by \(5\), a remainder of \(1\) when divided by \(3\), and a remainder of \(4\) when divided by \(7\). What are all such numbers?

Two congruences

Suppose we want to solve

\[\begin{aligned} x &\equiv a_1 \pmod{n_1}, \\ x &\equiv a_2 \pmod{n_2}, \end{aligned}\]

where \(n_1\) and \(n_2\) are coprime. By Bézout’s identity there are integers \(m_1, m_2\) with

\[m_1 n_1+m_2 n_2=1 .\]

Then a solution is

\[x=a_1 m_2 n_2+a_2 m_1 n_1 .\]

To check this, note that \(m_2 n_2 = 1 - m_1 n_1 \equiv 1 \pmod{n_1}\), so \(x \equiv a_1 \pmod{n_1}\); similarly \(x \equiv a_2 \pmod{n_2}\).

Example

Solve

\[\begin{aligned} x &\equiv 2 \pmod{5}, \\ x &\equiv 1 \pmod{3}. \end{aligned}\]

Bézout’s identity for \(5\) and \(3\) can be taken as

\[5 \cdot 5 + (-8) \cdot 3 = 1,\]

so \(m_1 = 5\) and \(m_2 = -8\). Then

\[x = 2 \cdot (-8) \cdot 3 + 1 \cdot 5 \cdot 5 = -48 + 25 = -23 .\]

Any two solutions differ by a multiple of both \(5\) and \(3\), hence by a multiple of \(\operatorname{lcm}(5, 3) = 15\). So the general solution is

\[x \equiv -23 \equiv 7 \pmod{15}.\]

More congruences

The same method handles more congruences one at a time. Returning to the opening question,

\[\begin{aligned} x &\equiv 2 \pmod{5}, \\ x &\equiv 1 \pmod{3}, \\ x &\equiv 4 \pmod{7}, \end{aligned}\]

the first two congruences combine to \(x \equiv 7 \pmod{15}\), so it remains to solve

\[\begin{aligned} x &\equiv 7 \pmod{15}, \\ x &\equiv 4 \pmod{7}. \end{aligned}\]

Now \(1 \cdot 15 + (-2) \cdot 7 = 1\), so \(m_1 = 1\), \(m_2 = -2\), and

\[x = 7 \cdot (-2) \cdot 7 + 4 \cdot 1 \cdot 15 = -98 + 60 = -38 .\]

Hence the solution is

\[x \equiv -38 \equiv 67 \pmod{105}.\]

Indeed, \(67 = 13 \cdot 5 + 2 = 22 \cdot 3 + 1 = 9 \cdot 7 + 4\).

Conclusion

This is an instance of the Chinese remainder theorem: if \(n_1, \ldots, n_k\) are pairwise coprime, the system \(x \equiv a_i \pmod{n_i}\) has a solution, unique modulo \(n_1 n_2 \cdots n_k\). The theorem has applications throughout number theory, modular arithmetic and cryptography; for example, it is used to speed up RSA decryption.

Changes on 25 October 2026

What was wrong. Nothing. The explanation of why the formula works was brief.

What changed. I added that explanation and a check that 67 satisfies all three congruences. Previously titled “Solving a system of Congruences”.