The Chinese Remainder Theorem gets its name from a 3rd century book written by the Chinese mathematician Sun Tzu. There are more details available on wikipedia.
In essence, it is a theorem about simultaneous congruences (see here if you need a review of modular arithmetic).
In today's blog, I will show the proof as it relates to standard integers.
Theorem: Chinese Remainder Theorem
Let ai be a set of set of k integers consisting of a1, a2, ..., ak.
Let ni be a set of k coprime integers consists of n1, n2, ..., nk where for any i,j if i ≠ j, then gcd(ni,nj)=1. [See here for review of greatest common divisor if needed]
Then, there exists an integer x such that for each ai, ni:
x ≡ a1 (mod n1)
x ≡ a2 (mod n2)
x ≡ ak (mod nk)
(1) Let n = n1 * n2 * ... * nk
(2) Let ci = n / ni for i = 1, ..., k
(3) We see that for all i, gcd(ci,ni) = 1 since:
(a) Assume gcd(ci,ni)=d where d is a number greater than 1.
(b) Then there exists a prime p that divides d (By the Fundamental Theorem of Arithmetic, see here)
(c) Since ci = n1 * ... * nk, by Euclid's Generalized Lemma (see here), p must divides nj where j ≠ i.
(d) But this impossible since by assumption gcd(ni,nj) = 1 when i ≠ j.
(e) So we reject that assumption in #2a.
(4) We further see that for all i,j when i ≠ j, nj divides ci.
This follows directly from ci = n / ni.
Which means that:
ci ≡ 0 (mod ni)
(5) Using Bezout's Identity (see here) and step #3, we know that for each ci, ni, there exists integers di,ei such that:
cidi + eini = 1.
(6) But this means that cidi ≡ 1 (mod ni) since cidi - 1 = (-ei)ni
(7) Let x = a1c1d1 + a2c2d2 + ... + aicidi + ... + akckdk
(8) We can show that x satisfies the assumption of the theorem since for any i:
x ≡ a1(0)d1 + a2(0)d2 + ... + ai(1) + ... + ak(0)dk ≡ ai (mod ni)