求3^4,3^5,...,除以17的余数不用把它们算出来的,利用同余式得性质会简化计算的.
a≡b(modm)
c≡d(modm)
则ac≡bd(modm),特别的由a≡b(modm)可知a^n≡b^n(modm).
3^2≡9(mod17)
3^4≡81≡-4(mod17)
3^8≡(-4)^2≡-1(mod17)
3^16≡(-1)^2≡1(mod17)
你要是知道费马小定理这个题就非常容易了.
费马小定理：
p是一个质数,p不整除a,那么：
a^(p-1)≡1(modp)
对于本题,17是个质数,3不是17的倍数,所以3^16≡1(mod17)
3^38=3^32*3^6≡1*9*(-4)≡15(mod17)