info prev up next book cdrom email home

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)
\end{displaymath} (1)

N\equiv b\ \left({{\rm mod\ } {s}}\right).
\end{displaymath} (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)
\end{displaymath} (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),
\end{displaymath} (4)

M\equiv m_1m_2\cdots m_r
\end{displaymath} (5)

and the $b_i$ are determined from
b_i{M\over m_i} \equiv 1 {\rm\ (mod\ } m_i).
\end{displaymath} (6)


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.

© 1996-9 Eric W. Weisstein