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

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

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

　　４１＝１＋２^3＋２^5

　　４１^41＝４１^（１＋２^3＋２^5）＝４１・４１^（２^3）・４１^（２^5）

　　４１^2＝１６８１＝３６

　　４１^（２^2）＝（４１^2）^2＝１２９６＝２７

　　４１^（２^3）＝（（４１^2）^2）^2）＝７２９＝２４

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

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

　　４１^41＝４１^（１＋２^3＋２^5）＝４１・４１^（２^3）・４１^（２^5）＝４１・２４・３＝２９５２＝３８＝-９

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