2的2013次方mod101是多少在卷子上怎么解，有巧妙方法？2^1000=16^250=(13+3)^250从而2^1000=3^250(mod13)为什么？同余理论？

Question

2的2013次方mod101是多少
在卷子上怎么解，有巧妙方法？
2^1000=16^250=(13+3)^250
从而　2^1000=3^250 (mod13)
为什么？同余理论？

Answer 1

馀数运算不考虑商
2^2013=2^(13+100*20)
= (2^13)*(2^100)^20
=========================
2^100 = (2^10)^10=(1010+14)^10 ≡14^10 (mod 101)
14^10 = (14^2)^5=(202-6)^5≡6^5 (mod 101)
6^5=6^3*6^2=(202+14)(36)≡14*36(mod 101)≡(505-1)(mod 101)≡1 (mod 101)
=========================
所以 2^13*(2^100)^20
=2^13*(2^100)^20≡(2^13) (mod 101)
(2^13)=8192=8181+11=101*81+11≡11 (mod 101)