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

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

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

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

  42=2+2^3+2^5

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

  42^2=1764=25

  42^(2^2)=(42^2)^2=625=14

  42^(2^3)=((42^2)^2)^2)=196=8

  42^(2^4)=(((42^2)^2)^2)^2)=64=17

  42^(2^5)=((((42^2)^2)^2)^2)^2)=289=7

  42^42=42^(2+2^3+2^5)=42^2・42^(2^3)・42^(2^5)=25・8・7=1400=37=-10

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