■フェルマーの小定理と剰余の計算（その１１）
［Ｑ］４０^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）＝１６・１８＝２８８＝６
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
