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

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

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

　　３７＝１＋２^2＋２^5

　　３７^37＝３７^（１＋２^2＋２^5）＝３７・３７^（２^2）・３７^（２^5）

　　３７^2＝１３６９＝６

　　３７^（２^2）＝（３７^2）^2＝３６

　　３７^（２^3）＝（（３７^2）^2）^2）＝１２９６＝２７

　　３７^（２^4）＝（（（３７^2）^2）^2）^2）＝７２９＝２４

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

　　３７^37＝３７^（１＋２^2＋２^5）＝３７・３７^（２^2）・３７^（２^5）＝１５９８４＝４

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