The Chinese Remainder Theorem says that certain systems of simultaneous congruences with different moduli have solutions. The idea embodied in the theorem was apparently known to Chinese mathematicians a long time ago --- hence the name.
I'll begin by collecting some useful lemmas.
Lemma 1. Let m and , ..., be positive integers. If m is relatively prime to each of , ..., , then it is relatively prime to their product .
Proof. If , then there is a prime p which divides both m and . Since , p must divide for some i. Now p divides both m and , so \contra. This contradiction implies that .
Example. 6 is relatively prime to 25, to 7, and to 11. , and :
I showed earlier that the greatest common divisor of a and b is greatest in the sense that it is divisible by any common divisor of a and b. The next result is the analogous statement for least common multiples.
Lemma 2. Let m and , ..., be positive integers. If m is a multiple of each of , ..., , then m is a multiple of .
Proof. By the Division Algorithm, there are unique numbers q and r such that
Now divides both m and , so divides r. Since this is true for all i, r is a common multiple of the smaller than the least common multiple . This is only possible if . Then , i.e. m is a multiple of .
Example. 88 is a multiple of 4 and 22. The least common multiple of 4 and 22 is 44, and 88 is also a multiple of 44.
Lemma 3. Let , ..., be positive integers. If , ..., are pairwise relatively prime (that is, for ), then
Proof. Induct on n. The statement is trivially true for , so I'll start with . The statement for follows from the equation :
Now assume , and assume the result is true for n. I will prove that it holds for .
Claim: .
(Some people take this as an iterative definition of .) is a multiple of each of , ..., , so by Lemma 2 it's a multiple of . It's also a multiple of , so
On the other hand, for ,
Therefore,
Obviously,
Thus, is a common multiple of all the 's. Since is the least common multiple, Lemma 2 implies that
Since I have two positive numbers which divide one another, they're equal:
This proves the claim.
Returning to the proof of the induction step, I have
The second equality follows by the induction hypothesis (the statement for n). The third equality follows from Lemma 1 and the result for .
Example. 6, 25, and 7 are relatively prime (in pairs). The least common multiple is .
Theorem. ( The Chinese Remainder Theorem) Suppose , ..., are pairwise relatively prime (that is, for ). Then the system of congruences
has a unique solution mod .
Notation.
means the product with omitted. For example,
This is a convenient (and standard) notation for omitting a single variable term in a product of things.
Proof. Define
That is, is the product of the m's with omitted. By Lemma 1, . Hence, there are numbers , such that
In terms of congruences,
Now let
If , then , so mod all the terms but the k-th term die:
This proves that x is a solution to the system of congruences (and incidentally, gives a formula for x).
Now suppose that x and y are two solutions to the system of congruences.
Then
Thus, is a multiple of all the m's, so
But the m's are pairwise relatively prime, so by Lemma 3,
That is, the solution to the congruences is unique mod .
Example. Solve
, so there is a unique solution mod 36. Following the construction of x in the proof,
Solution:
Example. Solve
The moduli are pairwise relatively prime, so there is a unique solution mod 60. This time, I'll solve the system using an iterative method.
But , so
Hence,
Finally, , so
Hence, .
Now put everything back:
Example. Calvin Butterball keeps pet meerkats in his backyard. If he divides them into 5 equal groups, 4 are left over. If he divides them into 8 equal groups, 6 are left over. If he divides them into 9 equal groups, 8 are left over. What is the smallest number of meerkats that Calvin could have?
Let x be the number of meerkats. Then
From , I get . Plugging this into the second congruence, I get
Hence, . Plugging this into gives
Plugging this into the third congruence, I get
Hence, . Plugging this into gives
The smallest positive value of x is obtained by setting , which gives .
You can sometimes solve a system even if the moduli aren't relatively prime; the criteria are similar to those for solving system of linear Diophantine equations. I'll state the result, but omit the proof.
Theorem. Consider the system
Note that if , case (b) automatically holds, and --- i.e. I get the Chinese Remainder Theorem for .
Example. Solve
Since , there is a unique solution mod . I'll use the iterative method to find the solution.
Since ,
Now I use my rule for "dividing" congruences: 6 divides both 12 and 6, and , so I can divide through by 6:
Multiply by 2, and convert the congruence to an equation:
Plug back in:
Send comments about this page to: Bruce.Ikenaga@millersville.edu.
Copyright 2008 by Bruce Ikenaga