modの計算

質問

x=(123^97)mod187を計算せよ。
という問題なのですが、答えがx=106になるらしいのですが、どうしたらこの答えを導き出せるのでしょうか？

187=11×17
φ(187)=(11-1)(17-1)=160
オイラーの定理より
123^160≡1(mod 187)
という風に考えたのですが…指数が最初の97より大きくなってしまったので、これではダメな気がして…。

教えていただけると助かります。
よろしくお願いします。

回答No.3

R_Earl · ベストアンサー

123^1 = 123 (mod 187)
123^2 = 169 (mod 187)
123^4 = (123^2)^2 = 169^2 = 137 (mod 187)
123^8 = (123^4)^2 = 137^2 = 69 (mod 187)
……
123^64 = (123^32)^2 = … = 137 (mod 187)

∴123^97 = (123^64) × (123^32) × (123^1) = … = 106 (mod 187)

お礼

アドバイスありがとうございます。

R_Earlさんのやり方で解くことができました。ありがとうございました。

回答No.2

koko_u_

>x=a*bにでもなるんでしょうか…。
なるかどうか、ちょっと考えればわかります

回答No.1

koko_u_

x ≡ a mod 11
x ≡ b mod 17

とのきに、x が mod 11×17 でいくつかわかりますか？

補足

アドバイスありがとうございます。
すみません、分からないです。
x=a*bにでもなるんでしょうか…。