（-2）^30≡22（mod 1002）の理由は？

質問

（-2）^30≡22　（mod 1002）となる理由がわかりません。
添付の2行目です。
（-2）^30
＝2^30
＝2^10＾3
＝1024＾3
＝（1002＋22）^3
＝1002^3＋3・1002^2・22＋3・1002・22^2+22^3
など考えてみたものの，もう少し簡単な方法はないのでしょうか。

回答No.1

WiredLogic · ベストアンサー

添付された画像の方の式が間違っています。

10^3 ≡ -2 (mod 1002) は、勿論OKですが、
次の式は、合同式の両辺を 10乗して、
10^30 ≡ (-2)^10 でなければなりません。

で、テキスト側の式の変形の途中でやっているように、
(-2)^10 = 1024 ≡ 22 (mod 1002)
で、出てきます。