■整数であるか? (その35)

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

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

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

  37=1+2^2+2^5

  37^37=37^(1+2^2+2^5)=37・37^(2^2)・37^(2^5)

  37^2=1369=6

  37^(2^2)=(37^2)^2=36

  37^(2^3)=((37^2)^2)^2)=1296=27

  37^(2^4)=(((37^2)^2)^2)^2)=729=24

  37^(2^5)=((((37^2)^2)^2)^2)^2)=576=12

  37^37=37^(1+2^2+2^5)=37・37^(2^2)・37^(2^5)=15984=4

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