韓信點兵

中國古代韓信點兵有一套方法,也成為是古代的一種演算法思維,他是問兩個人一排餘一,三個人一排也餘一,五個人一排餘七,請問兵的數量最少有多少個?
ans:
x ≡ 1 mod 2
x ≡ 1 mod 3
x ≡ 2 mod 5 .... 答案是七個

這樣要怎麼運算,當數目越來越大時,更要有個公式來做運算~
if x 要滿足下列式子:
x ≡ r1 mod p1
x ≡ r2 mod p2
x ≡ r3 mod p3

x ≡ rn mod pn

then x ≡ N/Pi * ai * ri mod N
其中 N = p1 * p2 * ... * pn
(N/pi) * ai ≡ 1 mod pi

x≡2 mod 11
x≡4 mod 17
x≡20 mod 23

x≡(11*17*23/11)*a1*2 + (11*17*23/17)*a2 *4 + (11*17*23/23)*a3*20
mod 11 * 17 * 23
≡ (782a1 + 1012a2 + 3740a3) mod 4301

1. (11*17*23/11) *a1 ≡ 1 mod 11
a1 ≡ 2

2.(11*17*23/17) *a2 ≡ 1 mod 17
a2 ≡ 8

3.(11*17*23/23) *a2 ≡ 1 mod 23
a3 ≡ 8

所以原式 782*2 + 1012*8 +3740*8 mod 4301
≡ 39580 mod 4301
≡ 871 mod 4301 ..... 答案是 871

驗證 (871-2) /11 整除
(871-4)/17 整除
(871-20)/23 整除