Ask A Scientist Mathematics Archive

Author:      hasinoff 
What is the Chinese remainder theorem as it applies to solving equations
involving the modulus operator?

Response #:  1 of 1
Author:      hawley
Any introductory text on number theory should have this.  I quote from
Elementary Introduction to Number Theory by C. T. Long, D. C. Heath & Co.,
1965.
"The Chinese Remainder Theorem: if (Mi,Mj) = 1 for  i != j, then the system 
x == C1 (mod M1), x == C2 (mod M2), . . . ,  x == Cr (mod Mr)  is solvable
and the solution is unique modulo M where M = M1 * M2 * ... * Mr. . . . 
Such problems were studied in antiquity, particularly by ancient Chinese
mathematicians, so the solution to the problem is called the Chinese
remainder theorem.
(above: I have used == for "is congruent to" and ! = for "not equal to")