剰余算

例えば、7^1024 mod 17
という計算、どうやってやればいいのでしょう？？

No.1 回答者： miocute 回答日時： 2010/01/27 20:05

7^1024 mod 17=(7^2)^512 mod 17=49^512 mod 17

=(49-17*3)^512mod 17=(-2)^512mod 17=((-2)^4)^128mod 17
=(16-17)^128mod 17=1

No.2 ベストアンサー 回答者： momordica 回答日時： 2010/01/28 00:34

「フェルマーの小定理」とか知ってると簡単ですね。

　pを素数、aをpと互いに素な整数とすると、
　　　a^(p-1)≡1 (mod p)
　が常に成り立つ。

定理の証明などについては、ググってください。
この問題の場合、

　　7^16≡1 (mod 17)

となるので、

　　7^1024≡(7^16)^64 (mod 17)
　　　　　≡1^64
　　　　　≡1