Re: [理工] [離散]-數論

看板Grad-ProbAsk作者 (sodas)時間16年前 (2010/02/26 08:30), 編輯推噓2(2推 0噓 0→)
留言2則, 2人參與, 最新討論串5/9 (看更多)
※ 引述《bernachom (Terry)》之銘言： : 請教一下 : 5^2003 mod 1001 : 求出來是2嗎? : 感覺很奇怪... : 謝謝幫忙 根據Euler定理 其實我自己是記小費馬定理進化版XD Fermat's Little Theorem: gcd(m,n)=1, n is a prime --> m^(n-1)=1 mod n Euler's Theorem: gcd(m,n)=1, n >0 --> m^phi(n)=1 mod n 其中phi(n)=Euler phi函數 而若n是質數 則phi(n)就是n-1 所以說是進化版XD 1001=7*11*13 phi(1001)=720 5^720 = 1 mod 1001 5^1440 = 1 mod 1001 5^2003 = 5^563 * 5^1440 = 5^563 mod 1001 因為7,11,13兩兩互質 故 可拆解成三個式子 5^563 mod 7 --> --> 3 mod 7 5^563 mod 11 --> Fermat little --> 4 mod 11 5^563 mod 13 --> --> 8 mod 13 解模同餘方程後可得所求為 3*143*5+4*91*4+8*77*12 = 10993 = 983 mod 1001 用Wolfram Alpha算也是983 所以應該沒錯 http://www.wolframalpha.com/input/?i=5%5E2003+mod+1001 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.39.21.164 ※ 編輯: sodas2002 來自: 114.39.21.164 (02/26 08:32)
推
02/26 08:45, , 1F
強者
02/26 08:45, 1F
推
02/26 11:39, , 2F
謝謝嚕^^
02/26 11:39, 2F
‣ 更多 sodas2002 的文章
文章代碼(AID): #1BXnOZWp (Grad-ProbAsk)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 5 之 9 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共9篇)
‣ 更多 sodas2002 的文章
文章代碼(AID): #1BXnOZWp (Grad-ProbAsk)