PineWiki
1. The Chinese Remainder Theorem
The Chinese Remainder Theorem, in the form typically used today, says that if m1 and m2 are relatively prime (i.e. gcd(m1,m2) = 1), then for each pair of equations n mod m1 = n1, n mod m2 = n2, there is a unique solution n with 0≤n<m1m2.
Example: let m1 = 3 and m2 = 4. Then the integers m from 0 to 11 can be represented as pairs (m1, m2) as follows:
m |
m1 |
m2 |
0 |
0 |
0 |
1 |
1 |
1 |
2 |
2 |
2 |
3 |
0 |
3 |
4 |
1 |
0 |
5 |
2 |
1 |
6 |
0 |
2 |
7 |
1 |
3 |
8 |
2 |
0 |
9 |
0 |
1 |
10 |
1 |
2 |
11 |
2 |
3 |
Proof: We will prove something stronger and show an isomorphism between ℤm and ℤm1×ℤm2, where ℤm1×ℤm2 is the set of pairs of elements (x,y) with addition defined by (x,y)+(x',y') = (x+x',y+y') and multiplication by (x,y)(x,y')=(xx',yy'). To go from ℤm to ℤm1×ℤm2, define f(n) = (n mod m1, n mod m2). Showing that f is an isomorphism requires showing it preserves addition and multiplication (i.e., that it is a homomorphism: f(a+b) = f(a)+f(b) and f(ab) = f(a)f(b)) and that it is bijective. For addition, observe that if a = kam1+a' and b = kbm1+b', then a+b mod m = a+b - xm for some x, which equals (ka+kb-xm/m1)m1+(a'+b')-xm=km1+(a'+b' mod m) for some k; thus, a+b mod m = (a mod m) + (b mod m) mod m. By symmetry, the same holds if we replace m1 by m2. For multiplication, perform the similar calculation ab mod m = ab - xm for some x, which equals (kam1+a')(kbm1+b')-xm = m1(kakb+kab'+kba'-xm/m1) + a'b' ≡m1 a'b' (and similarly for m2).
Now we must show that f is invertible. Let c1 = m2(m2-1 (mod m1)) and c2 = m1(m1-1 (mod m2)). (The inverses exist because gcd(m1,m2)=1.) These coefficients correspond to the pairs (1,0) and (0,1), because c1 = m2m2-1 = 1 (mod m1) and c1 = 0 (mod m2), and similarly for c1. So given (n1,n2), we can compute n = (n1c1+n2c2) mod m and have n mod m1 = n1*1 + n2*0 = n1 and n mod m2 = n1*0 + n2*1 = n2. We have just shown f is invertible, which implies it is an isomorphism.