韩信点兵 (中国剩余定理)

Chinese Remainder Theorem (CRT): 韩信点兵 (中国剩余定理)

China ‘Gauss’: 秦九韶 Qin Jiushao

A Southern Song dynasty (南宋) officer. During his 3-yr leaves when his mother died, he generalised 孙子算经 (4th century)’s “Chinese Remainder Theorem” in ‘大衍求一术’. After leaves, he went back to chase money & women, produced no more Maths.

Note: ‘求一’: solve a.X ≡ 1 (mod b); a < b

Chinese Remainder Theorem 中国剩余定理

X ≡ 2 (mod 3)
X ≡ 3 (mod 5)
X ≡ 2 (mod 7)
Solve X?

3人同行70稀
5树梅花21支
7子团圆半个月(15)

Let remainders:
$r_3=2, r_5=3, r_7=2$
$r= r_3.70+ r_5.21 + r_7.15 (mod 3.5.7)$
r= 2.70 +3.21 +2.15 (mod 105)
r= 140 +63 +30 (mod 105)
r= 233 (mod 105)
$r= 23 = x_{min}$
or X= 23 +105Z (23 + multiples of 105)

——————————————-
CRT: Why 3:70, 5:21, 7:15
X ≡ 2 (mod 3)
X ≡ 3 (mod 5)
X ≡ 2 (mod 7)

1) Find A such that
A ≡ 1 (mod 3)
A ≡ 0 (mod 5)
A ≡ 0 (mod 7)

=> 5|A, 7|A => 35 |A

A=35, 70 …
70 ≡ 1 (mod 3)
=> 70×2 ≡ 2 (mod 3)
2) Find B s.t.:
B ≡ 0 (mod 3)
B ≡ 1 (mod 5)
B ≡ 0 (mod 7)
3|B, 7|B => 21|B
21 ≡ 1 (mod 5)
=> 21×3 ≡ 3 (mod 5)
3) Find C s.t. :
C ≡ 0 (mod 3)
C ≡ 0 (mod 5)
C ≡ 1 (mod 7)
=> 3|C, 5|C => 15|C
=> C=15≡ 1 (mod 7)
15×2 ≡ 2 (mod 7)
4)
X ≡ 70×2 +21×3+ 15×2 (mod 3x5x7)
X≡ 233 (mod 105)
X≡ 23 (mod 105)
X= 23+105Z

—————-Ring Theory ——————————-
Commutative Ring CRT by Ring/ Ideal Theory:
If R is a commutative ring & A1,…An are pairwise coprime ideals,
Prove that if
$r_1, r_2, \cdots, r_n$ belong to R
Then there exists ‘a’ belongs to R with
$a + A_j= r_j + A_j$ ; j ∈[1,n]
Interpretation:
Let R= Z ring
X ≡ 2 (mod 3)
X ≡ 3 (mod 5)
X ≡ 2 (mod 7)
Or
X ≡ rj (mod mj)

Ideal = (m) = mZ
$A_3=(3), A_5=(5), A_7=(7)$
$r_3=2, r_5=3, r_7=2$
There exists
a=23
$a +A_3 = r_3 + A_3$
23+(3)= 2+ (3)
23 + 1×3 =2 + 8×3 =26