Chinese Remainder Theorem

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

$$N\equiv a\ \left({{\rm mod\ } {r}}\right)$$ (1)

and

$$N\equiv b\ \left({{\rm mod\ } {s}}\right).$$ (2)

Moreover, $N$ is uniquely determined modulo $rs$. An equivalent statement is that if $(r,s)=1$, then every pair of Residue Classes modulo $r$ and $s$ corresponds to a simple Residue Class modulo $rs$.

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

$$x\equiv a_i\ \left({{\rm mod\ } {m_i}}\right)$$ (3)

for $i=1$, ..., $r$ and for which the $m_i$ are pairwise Relatively Prime, the solution of the set of Congruences is

$$x=a_1b_1{M\over m_1}+\ldots+a_rb_r{M\over m_r}\ ({\rm mod\ } M),$$ (4)

where

$$M\equiv m_1m_2\cdots m_r$$ (5)

and the $b_i$ are determined from

$$b_i{M\over m_i} \equiv 1 {\rm\ (mod\ } m_i).$$ (6)

References

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.

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.