中国剩余定理CRT (Chinese Remainder Theorem)

X ≡ 2 (mod 3)

X ≡ 3 (mod 5)

X ≡ 2 (mod 7)

Solve X?

明. 程大位 “算法统宗” (1593)

3人同行70稀

5树梅花21支

7子团圆半个月(15)

除百零五(105)便得知

Let remainders:

$Latex r_3=2, r_5=3, r_7=2$

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

$latex 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

View original post 181 more words