[理工] 離散-中國餘數定理[用乘法反元素解]

[keke0421 (zrae)]

最近讀到小黃的離散的數論

有去補ＴＫＢ 但上課也聽不太懂 他在講解中國餘數定理那邊

http://imgur.com/sUZuFad

小黃那邊 沒有做什麼解釋 就直接這樣解 自己想個老半天 也想不懂

高中的時候

如下這題

x ≡ 2 (mod 3) ----(1)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

會利用同餘的加法原理 分成 3個部分 a , b ,c

先用a帶入1 其餘 餘數都是0  這樣a一定是5*7的倍數

接著35乘多少會mod 3餘2? 顯然答案是1

但小黃這個部分卻是-1

當然我知道答案其實最後加總起來是一樣的 但又不能一直用高中這套

畢竟有些題目 數字其實很難看 變成你一定要套小黃這套方式

但又無法理解 他用乘法反元素的做法 感覺不是很直觀 ＝＝

尤其是

上述連結的這三行

M1 ≡ Ｎ1^(-1) (mod n1 )
M2 ....etc

下面的部分也看不太懂

所以特來請教大大們 解惑ＱＱ





--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.214.242.230
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1441008444.A.3B4.html
※ 編輯: keke0421 (49.214.242.230), 08/31/2015 16:16:46
→ jerry031181: 你看他令N1 2 3的方式  一定會是另外兩個的倍數
→ jerry031181: 而且Mi為Ni的反元素 所以ri*Ni*Mi=ri 所以把三條式子
→ jerry031181: 個別代進去 eg mod n3  x mod n3就會只剩r3 因為其他
→ jerry031181: 其他兩項 N1  N2皆為n3的倍數所以為0 所以只剩r3這項
→ jerry031181: 忘記講了 Mi為Ni在ni下的反元素 所以當mod 不是ni時
→ jerry031181: Mi*Ni不會是1  所以Ni會是nj的倍數, j!=i