怎么求27^125除391的余数27^125(mod391)要给出详细过程谢谢了

Question

怎么求27^125除391的余数
27^125(mod391) 要给出详细过程 谢谢了

Answer 1

慢慢算咯
比如
27^2≡338（mod 391）
27^4≡338^2≡72(mod 391)
27^8≡72^2≡101(mod 391)
27^16≡101^2≡35(mod 391)
27^32≡35^2≡52(mod 391)
27^64≡52^2≡358(mod 391)
27^125=27^(64+32+16+8+4+1)≡358*52*35*101*72*27≡164(mod 391)
回答完毕,算的时候最好带上计算器,方便计算,呵呵