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

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

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

　　４０＝２^3＋２^5

　　４０^40＝４０^（２^3＋２^5）＝４０^（２^3）・４０^（２^5）

　　４０^2＝１６００＝２

　　４０^（２^2）＝（４０^2）^2＝４

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

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

　　４０^（２^5）＝（（（（３１^2）^2）^2）^2）^2)＝４４１＝１８

　　４０^40＝４０^（２^3＋２^5）＝４０^（２^3）・４０^（２^5）＝１６・１８＝２８８＝６

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