Friday, June 23, 2006

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 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)

Proof:

(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)

QED

No comments :