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)
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)