Question

ゲスト

2000^2000を12で割った余りを求めよ

2000^2000≡8^2000(mod12)より
2000乗を取って余りは8だと思ったのですが違いました

答えは4です

どこを間違えているのかまた正しくして欲しいです

Answer 1

W.Y.

8の2000乗は 64の1000乗にするて
まだ合同式がつかえるよ。次は 4の1000乗かな

４の1000乗は 16の500乗で 合同式で 4の500乗

4の500乗は16の250乗 合同式で 4の250乗

ここまで読めばわかるかな？ 合同式で
4の〜乗が繰り返しでてきて、指数減ってるよな！

何回も繰り返すとあまりは4になるね。

ゲスト

なるほど！！

そうすると指数がなくなるまで計算しなくてはいけないのでしょうか？

W.Y.

基本はそうしたほうがいい！

でも三回くらい繰り返すとさ
あ、これ16→4→16→4繰り返すなと
考えれるやろ？
合同式で 4の〜乗になるから 最終てきに

合同式使って 4の一乗に行き着くなと指数みて思ってほしい！
あ、指数のへんかは

1000→500→250→125→4と4の62乗→4と4の31乗で32→16→8→4→2→1 かな。