Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Number Theory > Chinese Remainder Theorem

Additional topics in this section:

Extended Euclidean Algorithm

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.

A constructive way to find x

Let N = n1n2n3...nk.  Now, for each i, consider N/ni, which is the product of all the n's except ni.
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.

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 this Math Help site is Graeme McRae.