The Chinese Remainder Theorem is a statement about simultaneous congruences:

Suppose n₁, n₂, n₃, ..., n_k are pairwise coprime integers.  Then for any given integers a₁, a₂, a₃, ..., a_k, there exists an integer, x, which is the solution to the system of equations,

x = a₁ (mod n₁),
x = a₂ (mod n₂),
x = a₃ (mod n₃),
   . . .
x = a_k (mod n_k)

And if x is a solution to the system of equations, then x + kN, where N = n₁n₂n₃...n_k is also a solution.

A constructive way to find x

Let N = n₁n₂n₃...n_k.  Now, for each i, consider N/n_i, which is the product of all the n's except n_i.
Find the reciprocal, s_i, of each N/n_i (mod n_i) using the Extended Euclidean Algorithm.
That is, s_i N/n_i = 1 (mod n_i).  Also, s_i N/n_i = 0 (mod n_j) for all j not equal to i.
Let e_i = s_i N/n_i, so e_i=1 (mod n_i), but e_i=0 (mod n_j) for all j not equal to i.

Then x = e₁a₁ + e₂a₂ + e₃a₃ + ... + e_ka_k is a solution to the system of equations.

Internet References

Wikipedia: Chinese remainder theorem 

Related Pages in this website

Number Theory Glossary -- in particular:

pairwise coprime - a set of integers is pairwise coprime if no two elements of the set share any factor other than 1 or -1.

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]