利用欧拉定理可简化大指数的幂运算，2<sup>1000000</_睦霖题库

简答题利用欧拉定理可简化大指数的幂运算，2^1000000次方mod99。

正确答案： ∵gcd（2,99）=1
∴Φ（99）=Φ（3²×11）=3×(3-1) ×Φ(11)=60
由定理可知：2⁶⁰≡1 mod 99
又∵1000000=16666×60+40
∴2^1000000 mod 99≡2⁴⁰ mod 99≡1024⁴ mod 99≡34⁴ mod 99≡67² mod 99≡34
答案解析：
关注下方微信公众号，在线模考后查看

热门试题