Chinese Remainder Theorem

Let  and  be positive integers which are relatively prime and let  and  be any two integers. Then there is an integer  such that

(1)

and

(2)

Moreover,  is uniquely determined modulo . An equivalent statement is that if , then every pair of residue classes modulo  and  corresponds to a simple residue class modulo .

The Chinese remainder theorem is implemented in the Wolfram Language as ChineseRemainder[a1, a2, ...m1, m2, ...]. The Chinese remainder theorem is also implemented indirectly using Reduce in with a domain specification of Integers.

The theorem can also be generalized as follows. Given a set of simultaneous congruences

(3)

for , ...,  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)

REFERENCES:

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.