The Chinese Remainder Theorem (CRT) is a tool for solving problems involving modular arithmetic. The theorem is called the “Chinese” remainder theorem because the Chinese mathematician Sun Tsu stated a special case of the theorem sometime between 280 and 473 A.D. In its simplest form, the theorem says that if you want to solve a congruence (mod α β), you can solve it (mod α) and (mod β) separately, then combine the solutions to these sub-problems into a solution to the original problem, provided α and β are relatively prime.

More generally, the CRT says that the system of equations *x* ≡ *a*_{i} (mod *m _{i}*) has a common solution if the numbers

*m*

_{1},

*m*

_{2}, …,

*m*are relatively prime in pairs (i.e.

_{r}*m*and

_{i}*m*have no factors in common if

_{j}*i*≠

*j*). The solution is unique mod

*m*where

*m*is the product of the

*m*‘s. In a typical application, you may start with a problem stated (mod

_{i}*m*) and then factor

*m*into prime powers. Each of these prime powers is then an

*m*in the CRT. For example, to solve a congruence (mod 1400), you might set

_{i}*m*

_{1}= 8,

*m*

_{2}= 25,

*m*

_{3}= 7.

You can find an existence proof of the Chinese Remainder Theorem in any number theory book. Here I present an explicit solution given in Donald Knuth’s book Seminumerical Algorithms. For other algorithms and much more information on the CRT, see the book Chinese Remainder Theorem: Applications in Computing, Coding, and Cryptography. (In case it seems “coding” and “cryptography” are redundant, the book uses “coding” to refer to error-correcting codes, such as the way music is encoded on a CD, not secret codes, which would fall under cryptography.)

First we find numbers *y _{i}* such that

*y*≡ 1 (mod

_{i}*m*) and

_{i}*y*≡ 0 (mod

_{i}*m*) for

_{j}*i*≠

*j*. Then the sum

*a*

_{1}

*y*

_{1}+

*a*

_{2}

*y*

_{2}+ … +

*a*

_{r}*y*is the solution we’re looking for.

_{r}But how to find the *y _{i}*? We can let

*y*= (

_{i}*m*/

*m*)

_{i}^{φ(mi)}.

But what is φ and why does this work? The function φ is called the Euler phi function. For a positive integer *n*, φ(*n*) is the number of positive integers less than *n* and relatively prime to *n*. (I’ll explain how to compute it in a minute.) Euler proved that if two numbers *a* and *n* are relatively prime, then *a*^{φ(n)} ≡ 1 (mod *n*). Because *m*/*m _{i}* is relatively prime to

*m*,

_{i}*y*≡ 1 (mod

_{i}*m*). For

_{i}*j*≠

*i*,

*m*/

*m*is a multiple of

_{i}*m*and so

_{j}*y*≡ 0 (mod

_{i}*m*).

_{j}So how do you compute φ(*n*)? This is easy once you know two facts about this function. First, if α and β are relatively prime, then φ(α β) = φ(α) φ(β). Second, for a prime *p*, φ(*p*) = *p* − 1 and φ(*p ^{k}*) =

*p*−

^{k}*p*

^{k−1}for

*k*> 1. Putting these facts together, you can easily calculate φ(

*n*) once you have its factorization into prime powers.

The solution given here is not be the fastest way to compute a solution to the problem posed by the CRT, but it is interesting because it’s explicit. On the other hand, it’s not terribly inefficient. The term (*m*/*m _{i}*)

^{φ(mi)}can be calculated using no more than 2 log

_{2}φ(

*m*) multiplications using fast exponentiation.

_{i}
Awesome post, I’m an undergraduate mathematics major from northern CA who stumbled across your blog. I hope you continue to blog about such interesting subjects!