※ 引述《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 ≡ a_1 (mod 7)
X ≡ a_2 (mod 9)
X ≡ a_3 (mod 13)
概念上，很簡單就有幾條，我們就多弄幾個變數開關來調整，
但是變數之間如果會有相互影響，那就不好調，
所以我們就有一個像下面這樣子的概念：
令 X ≡ r_1*9*13 + r_2*7*13 + r_3*7*9 (mod 819)
其中 r_1,r_2,r_3 是待定的係數，
r_i 後面的乘數取法是使得只有第一個項沒有 7，
這樣一整串 mod 7之後，就只剩下 r_1*9*13；
即 X ≡ r_1*9*13 (mod 7) ，
題設又說 X ≡ a_1 (mod 7)，所以綜合這兩條後，
就有一個方程式：a_1 ≡ r_1*9*13 (mod 7)（注意 r_1是待定的變數，a_1是給定數）
兩邊同乘把 9*13 這個數在 mod 7 下的 inverse 就得到： r_1 的值了。
（這個動作就好像看到 5 = y*3，解y， 這樣一個方程式，
左右兩邊同乘 三分之一 一樣自然。）
按照同樣的原理，注意到 只有中間第二個項的乘數沒有 9，
所以這樣一整串 mod 9 之後，就剩 r_2 * 某某數 ；
然後像剛剛一樣那樣去弄，一樣可以決定 r_2。
接著 r_3 一樣去這樣做。
因為我們列式時，係數乘積缺項調得很巧妙，所以每個r_i不會互相干擾，
一次就處理一個，各各擊破就好。
所以再回過頭來看這些缺一個項的乘數的話，
如果 n=p_1*p_2*p_3*..*p_s， p_1>p_2>...>p_s，
當然我們可以寫成像下面這樣，
第一項缺p_1，所以就是 p_2*p_3*p_4*...*p_s
第二項缺p_2，所以就是 p_1 *p_3*p_4*...*p_s
第三項缺p_3，所以就是 p_1*p_2 *p_4*...*p_s
...
第 i 項缺 p_i，所以就是 p_1*p_2*...*p_{i-1} *p_{i+1}*p_{i+2}*...*p_s。
但這樣寫太不環保了，所以就用另一個除掉的方式來寫，
第一項缺p_1，所以就是原來的n除掉p_1就好了，即 n/p_1，
第二項缺p_2，所以就是原來的n除掉p_1就好了，即 n/p_2，
...
第i項缺p_i，所以就是原來的n除掉p_1就好了，即 n/p_i。
把上面講得那些，用全符號的方法，寫成一個正規的數學敘述證明。
差不多就是你講的那些表示法了。
相同的概念，還有 Lagrange Interpolating Polynomial，拉格蘭日內插多項式。
http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html
這個簡單講就是今天我們被給定像下面這樣的一個任務：
找一個多項式 f(x)，滿足 f(a_1)=b_1,f(a_2)=b_2,f(a_3)=b_3。
（跟你原來題設的：X除以7餘5，X除以9餘4，X除以13餘3 要求本質上很相似吧。）
然後拉格蘭日內插多項式告訴你說，這個東西，他有一個秒殺的方法，像他那樣造就好。
像上面那樣弄一弄，也就很自然地得到了，所謂的證明了。
本質來說這些東西跟我們學一元二次聯立方程組是差不多的概念，
比方說：雞兔同籠，已知雞跟兔子全部幾隻，又已知全部有幾隻腳，
然後我們被要求算出，到底雞和兔子各有幾隻。
這時候，我們就會開始列一個一元二次聯立方程組出來，接著解解解，就解出來了。
技術上來講，這邊同餘類的問題，就是要怎麼樣去假設變數，列式。
真正核心的關鍵，簡單講，就是只有：
弄成一堆變數 r_1,r_2,..,r_s 的 sum，係數部分第i項缺 p_i，利用題設去決定r_i。
至於 你的 2 的話，簡單講就是我們為了符號上使用的簡潔，
所以略過了一些本來要寫清楚的符號解釋。
這裡 M1 在(mod n1)下的N1的inverse，
意思就是說 我們把 在(mod n1)下的N1的inverse 同餘類找出來，
然後隨便抓一個這個同餘類的元素出來當代表，那個代表我們就叫 M_1。
所以 M_1 是個整數，那自然我們就可以考慮 mod其他數時，
這個整數所在的那個同餘類了。
其實，你如果有這個疑問的話，可能更早就發生了，一開始題設
X≡5 (mod7)
X≡4 (mod9)
X≡3 (mod13)
可能就碰到一個類似fu的不舒湖了，那這時候，我們是怎麼克服這個問題的？
就是照上面講的那樣，其實 X 是一個整數；
一個整數，我們自然要拿來 mod什麼都有意義了。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 182.235.182.218