Additional topics in this section:
The Chinese Remainder Theorem is a statement about simultaneous congruences:
Suppose n1, n2, n3, ..., nk are pairwise coprime integers. Then for any given integers a1, a2, a3, ..., ak, there exists an integer, x, which is the solution to the system of equations,
x = a1 (mod n1),
x = a2 (mod n2),
x = a3 (mod n3),
. . .
x = ak (mod nk)
And if x is a solution to the system of equations, then x + kN, where N = n1n2n3...nk is also a solution.
Let N = n1n2n3...nk. Now,
for each i, consider N/ni, which is the product of all the n's except
Find the reciprocal, si, of each N/ni (mod ni) using the Extended Euclidean Algorithm.
That is, si N/ni = 1 (mod ni). Also, si N/ni = 0 (mod nj) for all j not equal to i.
Let ei = si N/ni, so ei=1 (mod ni), but ei=0 (mod nj) for all j not equal to i.
Then x = e1a1 + e2a2 + e3a3 + ... + ekak is a solution to the system of equations.
Wikipedia: Chinese remainder theorem
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 this Math Help site is Graeme McRae.