[理工] [離散]-政大98-資科

看板Grad-ProbAsk作者 (ming)時間16年前 (2010/02/18 21:50), 編輯推噓6(6推 0噓 12→)
留言18則, 6人參與, 最新討論串1/1
Find the least positive integer x satisfying the congrucence x三 325^1329 mod 11 同餘題目@@"，我嚐試化簡成 7^433 mod 11 但都是質數無法解開 希望有高手可以教導一下囉~ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.171.31.250
推
02/18 22:03, , 1F
費馬小定理?
02/18 22:03, 1F
→
02/18 22:08, , 2F
@@"補依下計算基按出來是2
02/18 22:08, 2F
推
02/18 22:16, , 3F
提示 7^(11-1)三 mod 11 => 7^(10)三 mod 11 =>7^430+3
02/18 22:16, 3F
→
02/18 22:16, , 4F
1 1
02/18 22:16, 4F
→
02/18 22:24, , 5F
謝謝樓上喔...我就差不多做到這步驟，只是接下來我就不才
02/18 22:24, 5F
推
02/18 22:25, , 6F
325^10 = 1 mod 11
02/18 22:25, 6F
→
02/18 22:26, , 7F
所以(325^10)^132 = 1 mod 11
02/18 22:26, 7F
推
02/18 22:29, , 8F
接著兩邊同乘325^9
02/18 22:29, 8F
→
02/18 22:30, , 9F
=> (325^10)^132 *325^9 = 325^9 mod 11
02/18 22:30, 9F
推
02/18 22:32, , 10F
答案=2(mod 11) 就一直化~很麻煩
02/18 22:32, 10F
→
02/18 22:33, , 11F
因為(325^10)^132 = 1 所以只要算325^9 mod 11的值
02/18 22:33, 11F
→
02/18 22:33, , 12F
L大 325^10 是從小費馬的方法找出來的麼@@"
02/18 22:33, 12F
→
02/18 22:35, , 13F
是阿 因為325跟11互質 所以325^(11-1) = 1 (mod 11)
02/18 22:35, 13F
推
02/18 22:37, , 14F
請問到325^9以後 就得慢慢算了嗎= =
02/18 22:37, 14F
→
02/18 22:38, , 15F
5% 我小小的5% 祈求教授的同情
02/18 22:38, 15F
→
02/18 22:39, , 16F
325^9 慢慢用 6^9 → 慢慢化簡很快就出來了
02/18 22:39, 16F
→
02/18 22:39, , 17F
要算325^9 mod 11,得先從 325 mod 11 算起
02/18 22:39, 17F
→
02/18 22:40, , 18F
接著等式兩邊再一直取平方
02/18 22:40, 18F
‣ 更多 abc73021 的文章
文章代碼(AID): #1BVKMiAx (Grad-ProbAsk)