［Ｑ］３１^31　ｍｏｄ　４７，すなわち，３１^31を４７で割ったときの余りを求めよ．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

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

　　３１＝１＋２^2＋２^3＋２^4

　　３１^31＝３１^（１＋２+２^2＋２^3＋２^4）＝３１・３１^2・３１^（２^2）・３１^（２^3）・３１^（２^4）

　　３１^2＝９６１＝２１

　　３１^（２^2）＝（３１^2）^2＝４４１＝１８

　　３１^（２^3）＝（（３１^2）^2）^2）＝３２４＝４２

　　３１^（２^4）＝（（（３１^2）^2）^2）^2）＝１７６４＝２５

　　３１^（２^5）＝（（（（３１^2）^2）^2）^2）^2)＝６２５＝１４

　　３１^31＝３１^（１＋２^2＋２^3＋２^4）＝３１・３１^（２^2）・３１^（２^3）・３１^（２^4）

３１・２１・１８＝１１７１８＝１５

４２・２５＝１０５０＝１６

１５・１６＝２４０＝５

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝