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 ≡ ai (mod mi) has a common solution if the numbers m1, m2, …, mr are relatively prime in pairs (i.e. mi and mj have no factors in common if i ≠ j). The solution is unique mod m where m is the product of the mi‘s. In a typical application, you may start with a problem stated (mod m) and then factor m into prime powers. Each of these prime powers is then an mi in the CRT. For example, to solve a congruence (mod 1400), you might set m1 = 8, m2 = 25, m3 = 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 yi such that yi ≡ 1 (mod mi) and yi ≡ 0 (mod mj) for i ≠ j. Then the sum a1 y1 + a2 y2 + … + ar yr is the solution we’re looking for.
But how to find the yi? We can let yi = (m/mi)φ(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/mi is relatively prime to mi, yi ≡ 1 (mod mi). For j ≠ i, m/mi is a multiple of mj and so yi ≡ 0 (mod mj).
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 φ(pk) = pk – pk-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/mi)φ(mi) can be calculated using no more than 2 log2φ(mi) multiplications using fast exponentiation.
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!