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

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

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

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

  28=2^2+2^3+2^4

  28^28=28^(2^2+2^3+2^4)=28^(2^2)・28^(2^3)・28^(2^4)

  28^2=784=32

  28^(2^2)=(28^2)^2=1024=37

  28^(2^3)=((28^2)^2)^2)=1369=6

  28^(2^4)=(((28^2)^2)^2)^2)=36

  28^28=28^(2^2+2^3+2^4)=28^(2^2)・28^(2^3)・28^(2^4)=7992=2

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