Let r and s be positive integers which are relatively prime and let a and b be any two integers. Then there is an integer N such that
 |
(1) |
and
 |
(2) |
Moreover, N is uniquely determined modulo rs. An equivalent statement is that if 
,
The Chinese remainder theorem is implemented as ChineseRemainder[{a1, a2, ...}{m1, m2, ...}] in the Mathematica add-on package NumberTheory`NumberTheoryFunctions` (which can be loaded with the command <<NumberTheory`). The Chinese remainder theorem is also implemented indirectly using Reduce starting in Mathematica Version 5.0 in with a domain specification of Integers.
The theorem can also be generalized as follows. Given a set of simultaneous congruences
 |
(3) |
for i = 1, ..., r and for which the 
are pairwise relatively prime, the solution of the set of
congruences is
 |
(4) |
where
 |
(5) |
and the 
are determined from
 |
(6) |
Congruence, Congruence Equation, Linear Congruence Equation
Flannery, S. and Flannery, D. In Code: A Mathematical Journey. London: Profile Books, pp. 123-125, 2000.
Ireland, K. and Rosen, M. "The Chinese Remainder Theorem." §3.4 in A Classical Introduction to Modern Number Theory, 2nd ed. New York: Springer-Verlag, pp. 34-38, 1990.
Séroul, R. "The Chinese Remainder Theorem." §2.6 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 12-14, 2000.
Uspensky, J. V. and Heaslet, M. A. Elementary Number Theory. New York: McGraw-Hill, pp. 189-191, 1939.
Wagon, S. "The Chinese Remainder Theorem." §8.4 in Mathematica in Action. New York: W. H. Freeman, pp. 260-263, 1991.
 |
|||
|
|
||