※ 引述《dknychou (dknychou)》之銘言：
: 2^40 mod 10 = ?
: <解>
: 2^40 mod 10
: = (2^10 * 2^10 * 2^10 * 2^10) mod 10 <-- 第一行
: = [(2^10 mod 10)*(2^10 mod 10)*(2^10 mod 10)*(2^10 mod 10)] mod 10 <-- 第二行
: = (4 * 4 * 4 * 4) mod 10 = 6
: 請教一下,這應該算是模數(modulus)的問題吧
: 從第一行變到第二行我不太瞭解為什麼可以這樣變,是模數有什麼性值或是特性嗎?
看到原po的文章
讓我想到另外兩種mod的題型
題型一
利用Euler totient function和Euler's Theorem來解
至於上述這兩項可以到下列網址查(因為有些符號不太好打)
(http://0rz.net/ea1AL 引用台科大電子商務研究中心的教學文件)
ex： 3^2000 mod 1999=9 由Euler totient function和Euler's Theorem得解
過程如下：
(3^1998)*(3^2) mod 1999
因為 3^1998=1 mod 1999 //根據Euler's Theorem
所以(3^1998)*(3^2) mod 1999 = 1*(3^2) mod 1999 = 9
題型二
2^31 mod (2^16+1)
= (2^16)*(2^15) mod (2^16+1) //又 2^16 mod (2^16+1)= -1
= (-1)*(2^15) mod (2^16+1)
= -(2^15) mod (2^16+1)
= 2^16+1-(2^15) mod (2^16+1) //想像成 1 mod 10 = (1+10) mod 10
= 2^15+1
我並非數學系或理工出身的
過程或觀念如果有錯誤請各位大大一起指正
謝謝 ^^
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.116.96.159