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

问题描述:

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

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)