剰余算

質問

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

回答No.2

momordica · ベストアンサー

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

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

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

　　7^16≡1 (mod 17)

となるので、

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

回答No.1

miocute

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