Question

100的1000次方除以13余数是几

运用费尔马小定理来计算，老师讲的迷迷糊糊的，我都晕了！对了，还有什么同余，什么mod

Answer 1

方法一，直接用同余性质：
100^1000
≡ 10^2000
≡ (-3)^2000
≡ (-27)^666 * (-3)^2
≡ (-1)^666 * 9
≡ 9 (mod 13)
不必用Fermat小定理。

方法二，如果非得用Fermat小定理a^(p - 1) ≡ 1 (mod p)：
容易看出：
100^1000 = 10^2000 = 10^166^12 * 10^8
对前一项用定理，后一项仍得用普通方法做：
10^166^12 * 10^8
≡ 1 * 10^8
≡ 10^8
≡ (-3)^8
≡ 3^8
≡ 3^3^2 * 3^2
≡ 27^2 * 3^2
≡ 1^2 * 3^2
≡ 9 (mod 13)

Answer 2

100/13=7.....9
100^1000≡9^1000(mod 13)
9^2/13=6.....3
9^1000≡81^500≡3^500(mod 13)
3^5/13=243/13=18.....9
3^500≡243^100≡9^100(mod 13)
9^2/13=6.....3
9^100≡81^50≡3^50(mod 13)
3^5/13=243/13=18.....9
3^50≡243^10≡9^10(mod 13)
9^2/13=6.....3
9^10≡81^5≡3^5(mod 13)
3^5(mod 13)=9
所以,100^1000≡9