The Chinese Remainder Theorem

Tags Math

The Chinese Remainder Theorem (CRT) is very useful in cryptography and other domains. According to Wikipedia, its origin and name come from this riddle in a 3rd century book by a Chinese mathematician:

There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?

Mathematically, this is a system of linear congruences. In this post we'll go through a simple proof of the existence of a solution. It also demonstrates how to find such a solution.

We'll start with a few prerequisite lemmas needed to prove the CRT. You may want to skip them on first reading and refer back when going through the CRT proof.

See my follow-up post on Computing the Chinese Remainder Theorem for a discussion of some computational approaches with full source code.

Prerequisites

Lemma 1: if d|ab and (d,a)=1, then d|b.

Proof: Since (d,a)=1 we know from Bézout's identity that there exist integers x and y such that dx+ay=1. Multiplying both sides by b, we get: bdx+bay=b. bdx is divisible by d, and so is bay because d|ab. Therefore d|b ∎

Lemma 2: if ac\equiv bc \pmod{m} and (c,m)=1, then a\equiv b \pmod{m}.

Proof: Since ac\equiv bc \pmod{m}, we know that m|(ac-bc), or m|c(a-b). Since (m,c)=1 we can use Lemma 1 to conclude that m|(a-b). In other words, a\equiv b \pmod{m} ∎

Modular multiplicative inverse

A modular multiplicative inverse of an integer a w.r.t. the modulus m is the solution of the linear congruence:

\[ax\equiv1 \pmod{m}\]

Lemma 3: if (a,m)=1 then a has a unique modular multiplicative inverse modulo m.

Proof: Once again using Bézout's identity, we know from (a,m)=1 that there exist integers r and s such that ar+ms=1. Therefore ar-1 is a multiple of m, or ar\equiv 1\pmod{m}. So r is a multiplicative inverse of a.

Now let's see why this inverse is unique. Let's assume there are two inverses, r_1 and r_2, so ar_1\equiv 1\pmod{m} and also ar_2\equiv 1\pmod{m}, which means that ar_1\equiv ar_2\pmod{m}.

Since (a,m)=1 we can apply Lemma 2 to conclude that r_1\equiv r_2\pmod{m} ∎

Factorization and multiplying moduli

Lemma 4: if a|n and b|n and (a,b)=1 then also ab|n.

Proof: Consider the prime factorization of n. a|n so a is a multiple of some subset of the these prime factors. The same can be said about b. But (a,b)=1, so a and b don't have any prime factors in common. Therefore ab is also a subset of the prime factors of n, and ab|n ∎

The Chinese Remainder Theorem

Assume n_1,\dots,n_k are positive integers, pairwise coprime; that is, for any i\neq j, (n_i,n_j)=1. Let a_1,\dots,a_k be arbitrary integers. The system of congruences with an unknown x:

\[\begin{align*} x &\equiv a_1 \pmod{n_1} \\ &\vdots \\ x &\equiv a_k \pmod{n_k} \end{align*}\]

has a single solution modulo the product N=n_1\times n_2\times \cdots \times n_k.

Proof: Let N_k=\frac{N}{n_k}. Then (N_k,n_k)=1, so each N_k has a unique multiplicative inverse modulo n_k per Lemma 3 above; let's call this inverse N'_k. Now consider:

\[x=a_1 N_1 N'_1+a_2 N_2 N'_2+\cdots +a_k N_k N'_k\]

N_k is a multiple of every n_i except for i=k. In other words for i\neq k we have N_i\equiv 0\pmod{n_i}. On the other hand, for i=k we have, by construction, N_i N'_i\equiv 1\pmod{n_i}. So for each k we have:

\[x\equiv a_k N_k N'_k \equiv a_k \pmod{n_k}\]

because all the other terms in the sum are zero. Hence x satisfies every congruence in the system.

To prove that x is unique modulo N, let's assume there are two solutions: x and y. Both solutions to the CRT should satisfy x\equiv y\equiv a_k\pmod{n_k}. Therefore x-y is a multiple of n_k for each k. Since these n_k are pairwise coprime, from Lemma 4 we know that x-y is also a multiple of N, or x\equiv y\pmod{N} ∎

Corollary

If n_1,\dots,n_k are pairwise coprime and N=n_1\times n_2\times \cdots \times n_k, then for all integers x and a, x\equiv a\pmod{n_i} for i=1,2,\dots,k if and only if x\equiv a\pmod{N}.

Proof: we'll start with the if direction. If x\equiv a\pmod{N} this means N|(x-a). But that immediately means that for each i, n_i|(x-a) as well, or x\equiv a\pmod{n_i}.

Now the only if direction. Given x\equiv a\pmod{n_i} for i=1,2,\dots,k, we can invoke the CRT using a in all congruences. The CRT tells us this system has a single solution modulo N. But we know that a is a solution, so it has to be the only one ∎

For comments, please send me an email.