Mon, 23 May 2005 12:57:00 EDT (-0400)

The Chinese Remainder Theorem (CRT) itself says that there exists a unique solution (but repeated modulus the product of the moduli) to a set of modular congruences if the moduli are relatively prime (i.e., gcd(mi,mj) = 1, if i not equal to j, where i and j are indicies each equal to one natural number in the range of 1 to the quantity of moduli, inclusive). Therefore it's easy to find proofs of existance and unicity all over the internet (Click here for a rant about this general tendency), but very difficult to find an explanation of why the CRT equation or formula used to calculate this works (I finally found a handout at the University of Hawaii (http://www.math.hawaii.edu/~lee/courses/Chinese.pdf) that gave me the idea, but even it didn't start with the math and then give an example).
The CRT equation (or formula) says that the sum of the products ri*(M/mi)*[((M/mi)^(-1)) mod mi] gives a solution to the congruences, and if the sum is taken mod M, the smallest such congruence is guaranteed. Each one of these terms can be reduced mod mi before summing and each factor in each term can also be reduced mod mi before multiplication  -- see page on background info.
mi is the "ith" modulus
ri is the "ith" residue or remainder when the solution is divided by mi
((M/mi)^(-1)) mod mi is the multiplicative inverse of M/mi wrt* mi
M is the product of all mi for all i.
i is an index equal to one natural number in the range of 1 to the quantity of moduli, inclusive.

(See page on background info for a little background on modular math)
The reason this equation works is that including the ratio M/mi first guarantees that the remainder of this term will be zero when divided by all of the other moduli (keep in mind that all mi are relatively prime) except for mi. Multiplying by the multiplicative inverse of M/mi (mod mi) guarantees that the remainder will be one when divided by mi (this is the definition of multiplicative inverse in modular number systems -- see page on background info). Multiplying by the desired residue ri for mi then gives the desired remainder when multiplied by the value of unity that results mod mi. This latter modular multiplication gives this result because of the theorem that the modulus of the product of  two numbers equals the modulus of the product of the same modulus of each of the two numbers -- see page on background info. The sum of the terms over all i gives all the desired residues mod all mi, because similarly the modulus of the sum of  two numbers equals the modulus of the sum of the same modulus of each of the two numbers. The terms that equal 0 mod mi thus do not interfere with the desired ri of the ith term. Taking modulus M reduces the congruence to the lowest correct value. Adding M repeatedly to that congruence generates an infinite number of valid congruences.

A search of the www can reveal that an ancient puzzle that this solved went as follows: a woman in a market place had a basket full of many eggs. Unfortunately, a passer-by was careless with his horse and accidentally knocked the basket out of the woman's hands, breaking all of the eggs. He offered to pay for the eggs, but how many were there? The only knowledge the woman had was that if the eggs were counted by twos, one was left over, counted by threes, two were left over, counted by fives, three were left over, and counted by sevens, four were left over.
We can solve this puzzle using an exhaustive search: the count by twos gives us that the quantity must have been odd. The count by threes gives us the congruences: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, ..., by fives gives us: 3, 8, 13, 18, 23, 28, 33, 38, ..., by sevens: 4, 11, 18, 25, 32...
As you can see, this might take a while, since 2*3*5*7 = 30*7=210, so we might have to write all numbers up to and including 209 (if 210 works, then 0 works, and we know there were not zero eggs).
Using the equation, for m1 = 2 we have r1=1, M/m1 = 105, and (M/m1)^-1 mod 2 = 105^-1 mod 2 = 1^-1 mod 2 = 1
for m2 = 3 we have r2=2, M/m2 = 70, and (M/m2)^-1 mod 3 = 70^-1 mod 3 = 1^-1 mod 3 = 1
for m3 = 5 we have r3=3, M/m3 = 42, and (M/m3)^-1 mod 5 = 42^-1 mod 5 = 2^-1 mod 5 = 3
and for m4 = 7 we have r4 = 4, M/m4 = 30, and (M/m4)^-1 mod 7 = 30^-1 mod 7 = 2^-1 mod 7 = 4.
We could have used Euclid's extended algorithm to calculate this, but it's easy when we realize that we can take the mod of the number before taking its inverse. (Click here to download a zipfile that contains the code for Euclid's extended algorithm, both exe (PCs) and source (Visual C++ ver 6.0 -- just using it in console mode, however).)
Therefore the first congruence is (1*105*1 + 2*70*1 + 3*42*3 + 4*30*4) mod 210 = (105 + 140 + 378 + 480) mod 210 = 1103 mod 210 = 53, and it's easy to check that this number gives us the desired remainders. So would 210 + 53, etc., but it should be easy to estimate these differences. You could also calculate the modulus of the terms first before adding them, to get (105 + 140 + 168 + 60) mod 210 =  473 mod 210 = 53. Hence the woman can judge whether she had 53 eggs or 263 eggs, etc.

Another ancient application of this was counting soldiers after a battle. The soldiers could be ordered to form groups of different sizes at a time and the commanding officers would only have to count the remainders of men left over that were standing next to them, and then do some figuring, rather than walking through the ranks doing a laborious one-by-one count that might be mistaken. A group of moduli could be chosen to give a value of M greater than the original number of soliders. This result could be a good check on the individual count. Of course if an elevated review point was available, the soldiers could simply be ordered to form groups of some number each, and then the groups could simply be counted along with any remainder. (This is why soldiers are organized into divisions, battalions, companies, platoons, and squads, etc.)

Modern applications include residue number systems (RNS), in which numbers are expressed in terms of the remainders, or residues, wrt a moduli set. Choosing the moduli set is an art, and modern papers have been written on this subject. Here's a good paper that you can look up on the IEEE website (http://www.ieeexplore.ieee.org): A signed-digit architecture for residue to binary transformation, Pourbigharaz, F., Yassine, H.M.; Computers, IEEE Transactions on, Volume: 46, Issue: 10, Oct. 1997 Pages: 1146 - 1150 - it gives a good moduli set that allows a nice fast converter (I have some simulation programs that demonstrate the nifty method that they invented). As you can see, converting the RNS number back to a positional number (such as binary, base ten, etc.) is laborious, but multiplication and addition are fast and easy in RNS. Division, sign detection and comparison are complex and slow. Overflow can be easily detected via some special techniques. Thus RNS are useful in DSP applications, and your digital camera might use this ancient modular math!.

*wrt = "with respect to" (See my Acronyms page)

Last updated Aug 21, May 23, 2005