［Ｑ］２^8911　ｍｏｄ　８９１１，すなわち，２^8911を８９１１で割ったときの余りを求めよ．

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

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

　　８９１１＝８９１０＝１＋２＋２^2＋２^3＋２^6＋２^7＋２^9＋２^13

　　２^8911＝２^（１＋２＋２^2＋２^3＋２^6＋２^7＋２^9＋２^13）＝２・２^2・２^（２^2）・２^（２^3）・２^（２^6）・２^（２^7）・２^（２^9）・２^（２^13）

２^2＝４，２^2^2＝１６，２^2^2^3＝１６^2＝２５６，

２^2^2^4＝２５６^2＝３１５９，

２^2^2^5＝３１５９^2＝−１０３９，

２^2^2^6＝１０３９^2＝１２９０，

２^2^2^7＝１２９０^2＝−２２５７，

２^2^2^8＝２２５７^2＝−３０４３，

２^2^2^9＝３０４３^2＝１３２０，

２^2^2^10＝１３２０^2＝４７５５，

２^2^2^11＝４７５５^2＝２８１８，

２^2^2^12＝２８１８^2＝１４２３，

２^2^2^13＝１４２３^2＝２１３２　　（ｍｏｄ８９１１） P />以上より

２^8910＝４・１６・２５６・１２９０・（−２２５７）・１３２０・２１３２＝１　　（ｍｏｄ８９１１）

２^8911＝２　　（ｍｏｄ８９１１）

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