Constructive proof of the Chinese Remainder Theorem

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 xai (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 ij). 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 ji, 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) = pkpk-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.

Related posts

One thought on “Constructive proof of the Chinese Remainder Theorem

  1. 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!

Leave a Reply

Your email address will not be published. Required fields are marked *