※ 引述《ericpoto (Eric)》之銘言：
: 初學CRT遇到了理解方面得障礙
: 我只理解取819是因為7.9.13互質
: 而7x9x13=819，則在mod819下有解
: 接下來就完全不理解了
: 題目如下：
: X≡5 (mod7)
: X≡4 (mod9)
: X≡3 (mod13)
: 解如下：
: r1=5,r2=4,r3=3
: n1=7,n2=9,n3=13
: n=n1n2n3=819
: N1=n/n1=117
: N2=n/n2=91
: N3=n/n3=63
: M1=N1¯(mod n1)=3
: M2=N2¯(mod n2)=1
: M3=N3¯(mod n3)=6
: 取X≡r1M1N1+r2M2N2+r3M3N3 (mod 819)
: 我的問題是
: 1.為何要取N1=n/n1,是為了甚麼準備?
: 2.M1不是在(mod n1)下的N1的inverse嗎?(類推M2.M3)
: 為何可以代入(mod n1n2n3)的式子中?
: 3.為何X≡r1M1N1+r2M2N2+r3M3N3 (mod 819)
這三個問題要一起回答

中國剩餘定理最早的出處是韓信點兵相信這你也知道

韓信點兵的原題以現代數學語言來寫就是:

已知 X≡r1 (mod 3) 求解 X
X≡r2 (mod 5)
X≡r3 (mod 7)

那一首歌謠解法若也寫成現代數學型式就是

X ≡ 70*r1 + 21*r2 + 15*r3 (mod 105)

這式子裡的 70 21 15 的地位就是上述公式解當中的 M1*N1 M2*N2 M3*N3

它所代表的意義是這樣的:

70≡1 (mod 3) 21≡0 (mod 3) 15≡0 (mod 3)
70≡0 (mod 5) 21≡1 (mod 5) 15≡0 (mod 5)
70≡0 (mod 7) 21≡0 (mod 7) 15≡1 (mod 7)

由此很容易驗證 X = 70*r1+21*r2+15*r3 確實滿足原來的三條同餘式

M1 跟 N1 等等的計算過程便是要找出對任意模數具有如上性質的乘數來

以第一直欄為例 n1 = 3, n2 = 5, n3 = 7

所以 N1 = n/n1 = n2*n3 = 35 可以被 n2 和 n3 整除 滿足了第一直欄下兩條

再來要找一個 N1 的倍數使得這個倍數除以 3 餘 1

所以就直接求 M1 = 35¯(mod 3) = 2 這即表示 2*N1 除以 3 會餘 1

所以 2*35 = 70 就是我們要找的第一個乘數 其餘的依此類推

這便是這一套公式的由來

(順帶一提, 這套演算法在古中國叫做「大衍求一術」

總結這套算法的是宋朝的數學家秦九韶

名字裡的「一」就是指上面的那些同餘表格中的那些餘一

大衍求一術就是在計算 M1*N1 等等的這些乘數的演算法)

--
◢ ˊ_▂▃▄▂_ˋ. ◣　　　　　 　　　　▅▅　▅▅　ι●╮　　 █▄▄▄▄▄
▍./◤_▂▃▄▂_◥ \'▊ 　　ＨＡＲＵＨＩ █████　＜■┘ 　 ▄▄▄▄▄▄▄
▎⊿ ◤◤◥█◥◥█Δ 　　ＩＳＭ　 　　By-gamejye　￠|\ 　　▌▌▌▌▌▄▌▌
▏ζ(▏●‵◥′●▊)Ψ ▏　　 　　　 　　　　█　　　 ⊿Δ 　　▄▄▄ ▄▄▄▄
█/|▊ 〃 、 〃▋ |\ ▎　　　　　 　 　ハルヒ主義　　　 　　█▄▄▄█▄▄
◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団　　　

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.41.19.119