■剰余の計算(その17)

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

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

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

  41=1+2^3+2^5

  41^41=41^(1+2^3+2^5)=41・41^(2^3)・41^(2^5)

  41^2=1681=36

  41^(2^2)=(41^2)^2=1296=27

  41^(2^3)=((41^2)^2)^2)=729=24

  41^(2^4)=(((41^2)^2)^2)^2)=576=12

  41^(2^5)=((((41^2)^2)^2)^2)^2)=144=3

  41^41=41^(1+2^3+2^5)=41・41^(2^3)・41^(2^5)=41・24・3=2952=38=-9

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