■剰余の計算(その15)

[Q]18^18 mod 47,すなわち,18^18を47で割ったときの余りを求めよ.

===================================

 反復2倍乗法を応用した反復平方による累乗法を用いると,

  18=2+2^4

  18^18=18^(2+2^4)=18^2・18^(2^4)

  18^2=324=42

  18^(2^2)=(18^2)^2=1764=25

  18^(2^3)=((18^2)^2)^2)=625=14

  18^(2^4)=(((18^2)^2)^2)^2)=196=8

  18^(2^5)=((((18^2)^2)^2)^2)^2)=64=17

  18^18=18^(2+2^4)=18^2・18^(2^4)=42・8=336=7

===================================