[理工] [離散]-數論

看板Grad-ProbAsk作者 (Terry)時間16年前 (2010/02/26 03:11), 編輯推噓3(3推 0噓 12→)
留言15則, 5人參與, 最新討論串3/9 (看更多)
請教一下 5^2003 mod 1001 求出來是2嗎? 感覺很奇怪... 謝謝幫忙 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.217.235.135 ※ 編輯: bernachom 來自: 61.217.235.135 (02/26 03:11)
推
02/26 03:25, , 1F
983
02/26 03:25, 1F
推
02/26 03:25, , 2F
我算出來是125耶..
02/26 03:25, 2F
推
02/26 03:29, , 3F
125
02/26 03:29, 3F
→
02/26 03:30, , 4F
125感覺很奇怪@@
02/26 03:30, 4F
→
02/26 03:31, , 5F
哪裡奇怪?
02/26 03:31, 5F
→
02/26 03:31, , 6F
沒這個選項QQ...
02/26 03:31, 6F
→
02/26 03:32, , 7F
因為5^1000 = 1 (mod1001)
02/26 03:32, 7F
→
02/26 03:32, , 8F
1001不是質數，可以用嗎?
02/26 03:32, 8F
→
02/26 03:33, , 9F
用費馬小定理gcd(5,1001)=1 =>5^(1001-1)=1(mod1001)
02/26 03:33, 9F
→
02/26 03:33, , 10F
我算5欸
02/26 03:33, 10F
→
02/26 03:33, , 11F
所以(5^1000)^2 * 5^3 = 125 (mod 1001)
02/26 03:33, 11F
→
02/26 03:34, , 12F
為什麼可以用費馬?1001又不是質數@@?
02/26 03:34, 12F
→
02/26 03:36, , 13F
喔喔 1001非質數的話就不能用了
02/26 03:36, 13F
→
02/26 03:38, , 14F
嗯..這樣不能用
02/26 03:38, 14F
→
02/26 04:13, , 15F
按計算機是983...
02/26 04:13, 15F
‣ 更多 bernachom 的文章
文章代碼(AID): #1BXijT9k (Grad-ProbAsk)
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 3 之 9 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共9篇)
‣ 更多 bernachom 的文章
文章代碼(AID): #1BXijT9k (Grad-ProbAsk)