Chinese Remainder Theorem, CRT, is one of the jewels of mathematics. It is a perfect combination of beauty and utility or, in the words of Horace, omne tulit punctum qui miscuit utile dulci. Known already for ages, CRT continues to present itself in new contexts and open vistas for new types of applications. So far, its usefulness has been obvious within the realm of “three C's”. Computing was its original field of application, and continues to be important as regards various aspects of algorithmics and modular computations. Theory of codes and cryptography are two more recent fields of application.
According to D. Wells, the following problem was posed by Sun Tsu Suan-Ching (4th century AD):
There are certain things whose number is unknown. Repeatedly divided by 3, the remainder is 2; by 5 the remainder is 3; and by 7 the remainder is 2. What will be the number?
Oystein Ore mentions another puzzle with a dramatic element from Brahma-Sphuta-Siddhanta (Brahma's Correct System) by Brahmagupta (born 598 AD):
An old woman goes to market and a horse steps on her basket and crashes the eggs. The rider offers to pay for the damages and asks her how many eggs she had brought. She does not remember the exact number, but when she had taken them out two at a time, there was one egg left. The same happened when she picked them out three, four, five, and six at a time, but when she took them seven at a time they came out even. What is the smallest number of eggs she could have had?
Problems of this kind are all examples of what universally became known as the Chinese Remainder Theorem. In mathematical parlance the problems can be stated as finding n, given its remainders of division by several numbers m1, m2, ..., mk:
(1) n = n1 (mod m1)
n = n2 (mod m2)
...
n = nk (mod mk)
The modern day theorem is best stated with a couple of useful notations. For non-negative integers m1, m2, ..., mk, their greatest common divisor is defined as
gcd(m1, m2, ..., mk) = max{s: s|mi, for i = 1, ..., k},
where, as always, "s|m" means that s divides m exactly. The least common multiple of k numbers is defined as
lcm(m1, m2, ..., mk) = min{s: s > 0 and mi|s, for i = 1, ..., k},
Both gcd() and lcm() are symmetric functions of their arguments. They are complementary in the sense that, for k = 2,
gcd(m1, m2)·lcm(m1, m2) = m1· m2.
(A proof and an interactive illustration for this identity appears elsewhere.)
However, for k > 2 a similar identity does not in general hold. For an example, consider two triplets: {2, 4, 16} and {2, 8, 16}. Both have exactly the same gcd and lcm but obviously different products. On the other hand, both gcd and lcm are associative:
gcd(m1, (gcd(m2, m3)) = gcd(gcd(m1, m2), m3)
and, both equal gcd(m1, m2, m3). Similarly,
lcm(m1, (lcm(m2, m3)) = lcm(lcm(m1, m2), m3)
Note
If, for a prime p, pαi|mi, with αi being the largest exponent with that property, then pα|lcm(m1, m2, ..., mk), where α = max{αi} and α is the largest exponent with that property. Similarly, the greatest common divisor of several numbers is the product of the largest powers of the primes that divide all the given numbers.
Associativity allows one to proceed a step at a time with an inductive argument without putting all eggs into a basket at once. Jumping at the opportunity I'll prove the most basic case of k = 2.
Theorem 1
Two simultaneous congruences
n = n1 (mod m1) and
n = n2 (mod m2)
are only solvable when n1 = n2 (mod gcd(m1, m2)). The solution is unique modulo lcm(m1, m2).
(When m1 and m2 are coprime their gcd is 1. By convention, a = b (mod 1) holds for any a and b.)
Proof
By a generalization of the Euclid's algorithm, there are integers s and t such that
tm1 + sm2 = gcd(m1, m2).
Since n2 - n1 = 0 (mod gcd(m1, m2)), for some, possibly different t and s,
(2)
tm1 + sm2 = n2 - n1.
Then n = tm1 + n1 = -sm2 + n2 satisfies both congruences in the theorem. This proves the existence of a solution.
To prove the uniqueness part, assume n and N satisfy the two congruences. Taking the differences we see that
N - n = 0 (mod m1) and N - n = 0 (mod m2)
which implies N - n = 0 (mod lcm(m1, m2)).
As was previously stated, a more general theorem can now be proved by induction.
Theorem 2
The simultaneous congruences (1)
n = n1 (mod m1)
n = n2 (mod m2)
...
n = nk (mod mk)
are only solvable when ni = nj (mod gcd(mi, mj)), for all i and j, i ≠ j. The solution is unique modulo lcm(m1, m2, ..., mk).
Proof
Theorem 1 serves the initial step verification. Assume the theorem holds for k congruences and consider k + 1 of them.
n = n1 (mod m1)
n = n2 (mod m2)
...
n = nk (mod mk)
n = nk+1 (mod mk+1)
Let s be a solution to the first k equations. Then the congrurence n = s (mod lcm(m1, m2, ..., mk)) has a solution. (Observe that every solution of the latter also satisfies the first k congruences.) To be able to apply the already proven Theorem 1, we need to show that
(3)
s = nk+1 (mod gcd(lcm(m1, ..., mk), mk+1)).
Let's write g u = gcd(m u, mk+1), u = 1, ..., k. Then we know that n u = nk+1 (mod g u) for these values of u. But n u = s + t um u, for some t u, implying nk+1 = s + t um u (mod g u) so that
s = nk+1 (mod g u), u = 1, 2, ..., k.
If so,
s = nk+1 (mod lcm(g1, ..., gk))
= nk+1 (mod lcm(gcd(m1, mk+1), ..., gcd(mk, mk+1))).
= nk+1 (mod gcd(lcm(m1, ..., mk), mk+1))
because lcm(gcd(m1, mk+1), ..., gcd(mk, mk+1)) = gcd(lcm(m1, ..., mk), mk+1).
Thus the system
n = s (mod lcm(m1, m2, ..., mk))
n = nk+1 (mod mk+1)
has a solution which is unique modulo lcm(lcm(m1, m2, ..., mk), mk+1) = lcm(m1, m2, ..., mk, mk+1). It also satisfies the whole set of k + 1 congruences.
Corollary
The simultaneous congruences (1)
n = n1 (mod m1)
n = n2 (mod m2)
...
n = nk (mod mk)
where all mi's are pairwise coprime has a unique solution modulo m1·m2· ... ·mk.
If some mi's are not mutually prime, a solution may not exist unless the corresponding congruence agree. For example, the system n = 1 (mod 2) and n = 2 (mod 4) has not solution, while the system n = 1 (mod 2) and n = ±1 (mod 4) does.
Let's now solve the two problems we started the page with.
Problem #1
Solve
p1: x = 2 (mod 3)
p2: x = 3 (mod 5)
p3: x = 2 (mod 7)
From p1, x = 3t + 2, for some integer t. Substituting this into p2 gives 3t = 1 (mod 5). Looking up 1/3 in the division table modulo 5, this reduces to a simpler equation
p4:
t = 2 (mod 5)
which, in turn, is equivalent to t = 5s + 2 for an integer s. Substitution into x = 3t + 2 yields x = 15s + 8. This now goes into p3: 15s + 8 = 2 (mod 7). Casting out 7 gives s = 1 (mod 7). From here, s = 7u + 1 and, finally, x = 105 u + 23.
Note that 105 = lcm(3, 5, 7). Thus we have solutions 23, 128, 233, ...
Problem #2
Solve
q1: x = 1 (mod 2)
q2: x = 1 (mod 3)
q3: x = 1 (mod 4)
q4: x = 1 (mod 5)
q5: x = 1 (mod 6)
q6: x = 0 (mod 7)
With the experience we acquired so far, the combination of q1-q5 is equivalent to
q7:
x = 1 (mod 60),
x = 60t + 1. Plugging this into q6 gives 60t = -1 (mod 7). Casting out 7 simplifies this to 4t = 6 (mod 7) and then 2t = 3 (mod 7). From the division tables modulo 7, 3/2 = 5 (mod 7). Therefore, t = 7u + 5. Finally, x = 420u + 301. Allowing for an average size farmer, the most likely number of eggs she might expect to be compensated for is 301.
Note: Chinese Remainder Theorem finds an important application in the clendrical calculations.
