※ 引述《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