Question

もか🌼

最初になぜ4に3乗しているのかと、4に198乗する理由を知りたいです。🙏

42009で割った余り
43=64=1 (modq)なので
4 (98 = (43) 66 = 166 (mod 9)
すなわち 41981 (mod 9 )
あって 4204199421.42=16ミク (mod9)
したがって 42009で割った余りは7

Answer 1

AZ

一般に,
mⁿ (m,n∈ℕ)をp(∈ℕ)で割った余りを求める場合,
mⁱ≡1 (mod p)となるi(∈ℕ)を探してみると効率がいいです.
iがmⁱ≡1 (mod p)　を満たし,
nをiで割ったときの商をj,余りをr(0≦r≦i-1)とすると,
n=ij+rより
mⁿ＝mⁱʲ⁺ʳ
＝mⁱʲ・mʳ
＝(mⁱ)ʲ・mʳ
≡1ʲ・mʳ (mod p)
＝mʳ