■フェルマーの小定理と剰余の計算（その８）
［Ｑ］３０^30 ｍｏｄ ４７，すなわち，３０^30を４７で割ったときの余りを求めよ．
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
反復２倍乗法を応用した反復平方による累乗法を用いると，
３０＝２＋２^2＋２^3＋２^4
３０^30＝３０^（２＋２^2＋２^3＋２^4）＝３０~2・３０^（２^2）・３０^（２^3）・３０^（２^4）
３０^2＝９００＝７
３０^（２^2）＝（３０^2）^2＝４９＝２
３０^（２^3）＝（（３０^2）^2）^2）＝４
３０^（２^4）＝（（（３０^2）^2）^2）^2）＝１６
３０^30＝３０^（２＋２^2＋２^3＋２^4）＝３０~2・３０^（２^2）・３０^（２^3）・３０^（２^4）＝８９６＝３
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
