[理工] [離散]中國餘數定理

看板Grad-ProbAsk作者 (lalalalalala)時間8年前 (2017/09/26 14:50), 8年前編輯推噓2(2推 0噓 5→)
留言7則, 3人參與, 最新討論串1/1
http://i.imgur.com/dBll0SW.jpg
想請問為什麼要使得 Mn≡Nn^(-1)(modnn) 還有下面算M 的部分也想不太透 後來看證明有理解M 跟N 了 但是還是想不到M 怎麼算 ----- Sent from JPTT on my Asus ASUS_Z017DA. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 117.19.208.5 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1506408649.A.0EC.html ※ 編輯: qwer911 (117.19.208.5), 09/26/2017 15:49:35
推
09/26 17:09, , 1F
mod的數字不大的話，可以用湊的
09/26 17:09, 1F
→
09/26 17:11, , 2F
否則就當成算乘法反元素，用Euclidean algorithm反推
09/26 17:11, 2F
→
09/26 19:30, , 3F
讀完第九章再回來看就很簡單了
09/26 19:30, 3F
推
10/01 13:43, , 4F
其實他的目標是要先找到某個數a_1同餘1 mod 2並且是3,5
10/01 13:43, 4F
→
10/01 13:43, , 5F
的倍數， a_2同餘1 mod 3並且是2,5的倍數, a_3同餘1 mo
10/01 13:43, 5F
→
10/01 13:43, , 6F
d5 並且是2,3的倍數，找到後如果依題目要x同餘2 mod 3,
10/01 13:43, 6F
→
10/01 13:43, , 7F
3 mod5, 2 mod 7， 只要取x=2a_1+3a_2+2a_3即可
10/01 13:43, 7F
‣ 更多 qwer911 的文章
文章代碼(AID): #1PoVZ93i (Grad-ProbAsk)