Question

求2的1000次方除以13的余数。 用同余的格式!!!

Answer 1

求2的1000次方除以13的余数。 用同余的格式!!!
解：
由欧拉函数定理或费马小定理，
2^12==1 mod 13
而1000=12*83+4
故2^1000==(2^12)^83*2^4==2^4==3 mod 13

另外也可以这样：
易见2^6==-1 mod 13
而1000=6*166+4
故2^1000=(-1)^166*2^4==3 mod 13

Answer 2

2^1000=16^250=(13+3)^250
从而　2^1000=3^250 (mod13)
3^250=3×3^249
3^249=27^(83)=(26+1)^83
从而　3^249 =1 (mod13)
所以　3^250 =3 (mod13)
即　　2^1000=3 (mod13)