✨ ベストアンサー ✨
13^100を9で割った余り
2000^2000を12で割った余りを求める問題ですよね？
ある程度合同式の性質はわかっているとしてすすめます。わからないところあれば聞いてください。
合同式の性質から、a≡b(mod m)が成り立つときはa^n≡b^n(mod m)も成り立ちます。これを使います。
13^100を9で割った余りは、13≡4(mod9)より、13^100≡4^100(mod9)です。
しかし、このままだとちょっと数は少なくなりましたが、それでも4^100を計算するのは困難です。そこで、累乗を計算できるようするために、1を作るしかありません。
4^1≡4(mod9)
4^2≡16≡7(mod9)
4^3≡4^1×4^2≡4×7≡1(mod9)
と順に試していくと、4^3で1が出てきました。この4^3はmod9のもとでは何乗しても1です。
よって4^100を(4^3)^33×4と考えることで4^99≡(4^3)^33≡1^33≡1(mod9)より、[(4^3)^33]×4≡1^33×4≡4(mod9)とすることができます。
(2)に関しても同じです。
8≡8(mod12)
8^2≡64≡4(mod12)
8^3≡8^1×8^2≡8×4≡-4(mod12)
8^4≡8^2×8^2≡4×4≡4(mod12)
8^5≡8^4×8^1≡8×4≡-4(mod12)
8^6≡8^4×8^2≡4×4≡4(mod12)
...
もうある程度規則はわかったと思いますが、4×4がmod12のもとでは4なので8^2が4で8^4が4×4≡4である以上、8^6が2乗と4乗で4×4≡4, 8^8が4乗と4乗で4×4≡4 ,8^10が6乗と4乗で4×4という風に、4×4の組み合わせが永久的にできていくので、絶対に偶数だと余りが4になります。よって、8^2000≡4(mod12)なので、2000^2000≡8^2000≡4(mod12)となります。
なるほど！ありがとうございました！
あ、そうです