初學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)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.34.121.68