法演算

質問

問題を解いていて分からないことがありましたので、質問させていただきます。

10^32(mod 7)を計算する問題なのですが、模範解答では

10^2≡3・10(mod 7)≡2(mod 7)
10^3≡2・10(mod 7)≡6(mod 7)
10^4≡6・10(mod 7)≡4(mod 7)
10^5≡4・10(mod 7)≡5(mod 7)
10^6≡5・10(mod 7)≡1(mod 7)
10^32≡10^6・10^6・10^6・10^6・10^6・10^2(mod 7)
≡2(mod 7)
となっているのですが、なぜこのような変形ができるのかの理屈が分かりません。
これはどのように計算しているのでしょうか？

分かる方がいらっしゃいましたら、よろしくお願いします。

回答No.1

age_momo

10=7+3　です。
これに10を掛けると
10*(7+3)=70+10*3≡10*3 (mod 7)
なので
10^2≡10*3 (mod 7)
です。同様に
10*3≡(7+3)*3≡3^2≡2 (mod 7)
となります。これ以降も同じです。

ところでフェルマーの小定理を持ち出すと
10と7は互いに素ですから

10^(7-1)=10^6≡1 (mod 7)

とすぐに分かります。

参考URL：

http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Fermat.html

お礼

回答ありがとうございます。
丁寧にご説明していただいたおかげで、理解することができました。