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

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

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

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

  11=1+2+2^3

  11^11=11^(1+2+2^3)=11・11^2・11^(2^3)

  11^2=121=27

  11^(2^2)=(11^2)^2=729=24

  11^(2^3)=((11^2)^2)^2)=576=12

  11^(2^4)=(((11^2)^2)^2)^2)=144=3

  11^(2^5)=((((11^2)^2)^2)^2)^2)=9

  11^11=11^(1+2+2^3)=11・11^2・11^(2^3)=11・27・12=3564=39=-8

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