Re: [代數]CRT 中國餘數定理
※ 引述《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
推
09/10 20:35, , 1F
09/10 20:35, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 4 篇)：