# The Chinese Remainder Theorem

Suppose we wish to solve

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

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

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

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,

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

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\).

*blynn@cs.stanford.edu*💡