Chinese remainder theorem

Last updated on 10/5/25

Before formally stating the theorem, let’s build up some intuition for the main result. Imagine that we have a natural number, \(n\), which is unknown, and suppose the only information we are given about the number is \[\begin{align*} n&\equiv 2 \text{ (mod 3)} \\ n &\equiv 1 \text{ (mod 2)} \end{align*}\]

Are we able to narrow down what values of \(n\) are possible given these two statements? Writing out some of the first numbers, we can begin to eliminate possible choices. First, all numbers that do not satisfy \(x\equiv 2 \text{ (mod 3)}\) - 2, 5, etc. - can be removed from the list of possible choices. \[\begin{equation*} \cancel{1} \quad 2 \quad \cancel{3} \quad \cancel{4} \quad 5 \quad \cancel{6} \end{equation*}\] Next, we remove all numbers that do not satisfy \(x\equiv 1 \text{ (mod 2)}\): \[\begin{equation*} \cancel{1} \quad \cancel{2} \quad \cancel{3} \quad \cancel{4} \quad 5 \quad \cancel{6} \end{equation*}\] Therefore, 5 is the only number less than 6 that satisfies the given modular relations.

Let’s try another example, this time with \[\begin{align*} n &\equiv 1 \text{ (mod 3)} \\ n&\equiv 2 \text{ (mod 5)} \end{align*}\] Crossing off number that do not satisfy the first relation, \[\begin{equation*} 1 \quad \cancel{2} \quad \cancel{3} \quad 4 \quad \cancel{5} \quad \cancel{6} \quad 7 \quad \cancel{8} \quad \cancel{9} \quad 10 \quad \cancel{11} \quad \cancel{12} \quad 13 \quad \cancel{14} \quad \cancel{15} \end{equation*}\] Now the second relation, \[\begin{equation*} \cancel{1} \quad \cancel{2} \quad \cancel{3} \quad \cancel{4} \quad \cancel{5} \quad \cancel{6} \quad 7 \quad \cancel{8} \quad \cancel{9} \quad \cancel{10} \quad \cancel{11} \quad \cancel{12} \quad \cancel{13} \quad \cancel{14} \quad \cancel{15} \end{equation*}\] Thus, 7 must be the only natural number less than 15 that satisfies the limited information given about \(n\).

What then do we notice from these two examples? Well, if we have an unknown integer which has known remainders for some given integers, then there is only one number less than the product of the dividing integers that satisfies the modular relationships. This is the main idea of the Chinese remainder theorem. A more formal statement follows.

The Chinese remainder theorem statement. (source)

Let \(n_1, \dots , n_k\) be integer divisors greater than 1, and let \(N=n_1n_2\dots n_i\). If all \(n_i\) are relatively prime (pairwise coprime), and if \(a_1, \dots, a_k\) are integers such that \(0\leq a_i < n_i\) for every \(i\), then there is one and only one integer \(x\) such that \(0\le x < N\) where the remainder of \(x / n\) is \(a_i\) for every \(i\).

Perhaps more clearly the theorem can be restated in terms of congruences. Using the same definitions as above, then the system \[\begin{align*} x &\equiv a_1 \text{ (mod } n_1 \text{)} \\ \vdots \\ x &\equiv a_k \text{ (mod } n_k \text{)} \end{align*}\] has a solution, and any two solutions \(x_1\) and \(x_2\) are congruent modulo \(N\): \[\begin{equation*} x_1 \equiv x_2 \text{ (mod N)} \end{equation*}\]