推 chenbojyh:強者 02/26 08:45
推 bernachom:謝謝嚕^^ 02/26 11:39
※ 引述《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)