Chinese Remainder Theorem
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:
| |
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.
|
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)
|
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
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
The first congruence is equivalent to n = tm1 + n1, the second to n = sm2 + n2, for some integers t and s. Equating we get
The left-hand side is divisible by gcd(m1, m2). So, unless the right-hand side is also divisible by gcd(m1, m2), there couldn't possibly exist t and s that satisfy the identity.
Now let's assume that gcd(m1, m2)|(n2 - n1) and denote n0 = (n2 - n1)/gcd(m1, m2). Then, (1) can be rewritten as
| |
t(m1/gcd(m1, m2)) - s(m2/gcd(m1, m2)) = n0
|
which implies
| (2) |
t(m1/gcd(m1, m2)) = n0 (mod (m2/gcd(m1, m2)))
|
By definition, m1/gcd(m1, m2) and m2/gcd(m1, m2) are coprime; for we divided m1 and m2 by their largest common factor.
Therefore, by a generalization of the Euclid's Proposition VII.30,
(2) has a solution. Given t, we can determine n = tm1 + n1. These proves the existence part.
To prove the uniqueness part, assume n and N satisfy the two congruences. Taking the differences we see that
| (3) |
N - n = 0 (mod m1) and N - n = 0 (mod m2)
|
which implies N - n = 0 (mod lcm(m1, m1)).
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
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
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
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.
References
- H. Davenport, The Higher Arithmetic, Cambridge University Press; 7 edition (December 9, 1999)
- P. J. Davis and R. Hersh, The Mathematical Experience, Houghton Mifflin Company, Boston, 1981
- R. Graham, D. Knuth, O. Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.
- Oystein Ore, Number Theory and Its History, Dover Publications, 1976
- D. Wells, The Penguin Book of Curious and Interesting Puzzles, Penguin Books, 1992
Copyright © 1996-2008 Alexander Bogomolny
|
