Chinese Remainder Theorem

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 a_i be a set of set of k integers consisting of a₁, a₂, ..., a_k.

Let n_i be a set of k coprime integers consists of n₁, n₂, ..., n_k where for any i,j if i ≠ j, then gcd(n_i,n_j)=1. [See here for review of greatest common divisor if needed]

Then, there exists an integer x such that for each a_i, n_i:

x ≡ a₁ (mod n₁)

x ≡ a₂ (mod n₂)

...

x ≡ a_k (mod n_k)

Proof:

(1) Let n = n₁ * n₂ * ... * n_k

(2) Let c_i = n / n_i for i = 1, ..., k

(3) We see that for all i, gcd(c_i,n_i) = 1 since:

(a) Assume gcd(c_i,n_i)=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 c_i = n₁ * ... * n_k, by Euclid's Generalized Lemma (see here), p must divides n_j where j ≠ i.

(d) But this impossible since by assumption gcd(n_i,n_j) = 1 when i ≠ j.

(e) So we reject that assumption in #2a.

(4) We further see that for all i,j when i ≠ j, n_j divides c_i.

This follows directly from c_i = n / n_i.

Which means that:

c_i ≡ 0 (mod n_i)

(5) Using Bezout's Identity (see here) and step #3, we know that for each c_i, n_i, there exists integers d_i,e_i such that:

c_id_i + e_in_i = 1.

(6) But this means that c_id_i ≡ 1 (mod n_i) since c_id_i - 1 = (-e_i)n_i

(7) Let x = a₁c₁d₁ + a₂c₂d₂ + ... + a_ic_id_i + ... + a_kc_kd_k

(8) We can show that x satisfies the assumption of the theorem since for any i:

x ≡ a₁(0)d₁ + a₂(0)d₂ + ... + a_i(1) + ... + a_k(0)d_k ≡ a_i (mod n_i)

QED