The Chinese Remainder Theorem

Suppose we wish to solve

\[ x = 2 \pmod{5} \]
\[ x = 3 \pmod{7} \]

for \(x\). If we have a solution \(y\), then \(y + 35\) is also a solution. So we only need to look for solutions modulo \(35\). By brute force, we find the only solution is \(x = 17 \pmod{35}\).

For any system of equations like this, the Chinese Remainder Theorem tells us there is always a unique solution up to a certain modulus, and describes how to find the solution efficiently.

Theorem: Let \(p, q\) be coprime. Then the system of equations

\[ x = a \pmod{p} \]
\[ x = b \pmod{q} \]

has a unique solution for \(x\) modulo \(p q\).

The reverse direction is trivial: given \(x \in \mathbb{Z}_{p q}\), we can reduce \(x\) modulo \(p\) and \(x\) modulo \(q\) to obtain two equations of the above form.

Proof: Let \(p_1 = p^{-1} \pmod{q}\) and \(q_1 = q^{-1} \pmod{p}\). These must exist since \(p, q\) are coprime. Then we claim that if \(y\) is an integer such that

\[ y = a q q_1 + b p p_1 \pmod{p q} \]

then \(y\) satisfies both equations:

Modulo \(p\), we have \(y = a q q_1 = a \pmod{p}\) since \(q q_1 = 1 \pmod{p}\). Similarly \(y = b \pmod{q}\). Thus \(y\) is a solution for \(x\).

It remains to show no other solutions exist modulo \(p q\). If \(z = a \pmod{p}\) then \(z - y\) is a multiple of \(p\). If \(z = b \pmod{q}\) as well, then \(z - y\) is also a multiple of \(q\). Since \(p\) and \(q\) are coprime, this implies \(z - y\) is a multiple of \(p q\), hence \(z = y \pmod {p q}\). ∎

This theorem implies we can represent an element of \(\mathbb{Z}_{p q}\) by one element of \(\mathbb{Z}_p\) and one element of \(\mathbb{Z}_q\), and vice versa. In other words, we have a bijection between \(\mathbb{Z}_{p q}\) and \(\mathbb{Z}_p \times \mathbb{Z}_q\).

Examples: We can write \(17 \in \mathbb{Z}_{35}\) as \((2,3) \in \mathbb{Z}_5 \times \mathbb{Z}_7\). We can write \(1 \in \mathbb{Z}_{p q}\) as \((1,1) \in \mathbb{Z}_p \times \mathbb{Z}_q\).

In fact, this correspondence goes further than a simple relabelling. Suppose \(x, y \in \mathbb{Z}_{p q}\) correspond to \((a,b), (c,d) \in \mathbb{Z}_p \times \mathbb{Z}_q\) respectively. Then a little thought shows \(x + y\) corresponds to \((a + c, b + d)\), and similarly \(x y\) corresponds to \((a c, b d)\).

A practical application: if we have many computations to perform on \(x \in \mathbb{Z}_{p q}\) (e.g. RSA signing and decryption), we can convert \(x\) to \((a,b) \in \mathbb{Z}_p \times \mathbb{Z}_q\) and do all the computations on \(a\) and \(b\) instead before converting back. This is often cheaper because for many algorithms, doubling the size of the input more than doubles the running time.

Example: To compute \(17 \times 17 \pmod{35}\), we can compute \((2\times 2,3\times 3) = (4,2)\) in \(\mathbb{Z}_5\times\mathbb{Z}_7\), and then apply the Chinese Remainder Theorem to find that \((4,2)\) is \(9 \pmod{35}\).

Let us restate the Chinese Remainder Theorem in the form it is usually presented.

For Several Equations

Theorem: Let \(m_1,...,m_n\) be pairwise coprime (that is \(\gcd(m_i, m_j) = 1\) whenever \(i \ne j\)). Then the system of \(n\) equations

\[ x = a_1 \pmod{m_1} \]
\[ ... \]
\[ x = a_n \pmod{m_n} \]

has a unique solution for \(x\) modulo \(M\) where \(M = m_1...m_n\).

Proof: This is an easy induction from the previous form of the theorem, or we can write down the solution directly.

Define \(b_i = M / m_i\) (the product of all the moduli except for \(m_i\)) and \(b'_i = b_i^{-1} \pmod{m_i}\). Then by a similar argument to before,

\[ x = \sum_{i=1}^n a_i b_i b'_i \pmod{M} \]

is the unique solution.∎

Prime Powers First

An important consequence of the theorem is that when studying modular arithmetic in general, we can first study modular arithmetic a prime power and then appeal to the Chinese Remainder Theorem to generalize any results. For any integer \(n\), we factorize \(n\) into primes \(n = p_1^{k_1} ... p_m^{k_m}\) and then use the Chinese Remainder Theorem to get

\[ \mathbb{Z}_n = \mathbb{Z}_{p_1^{k_1}} \times ... \times \mathbb{Z}_{p_m^{k_m}} \]

To prove statements in \(\mathbb{Z}_{p^k}\), one starts from \(\mathbb{Z}_p\), and inductively works up to \(\mathbb{Z}_{p^k}\). Thus the most important case to study is \(\mathbb{Z}_p\).


Ben Lynn blynn@cs.stanford.edu 💡