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

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

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

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

  43=1+2+2^3+2^5

  43^43=42^(1+2+2^3+2^5)=43・43^2・43^(2^3)・43^(2^5)

  43^2=1849=16

  43^(2^2)=(43^2)^2=256=21

  43^(2^3)=((43^2)^2)^2)=441=18

  43^(2^4)=(((43^2)^2)^2)^2)=324=42

  43^(2^5)=((((43^2)^2)^2)^2)^2)=1764=25

  43^43=42^(1+2+2^3+2^5)=43・43^2・43^(2^3)・43^(2^5)

=43・16・18・25=309600=11

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