Question

求3的100次方除以45的余数?

Answer 1

（1）先用同余吧,最喜欢了!
3^100
=81^25
≡36^25(mod 45)
≡1296^12×36(mod 45)
≡36^12×36(mod 45)
≡1296^6×36(mod 45)
≡36^6×36(mod 45)
≡1296^3×36(mod 45)
≡36^3×36(mod 45)
≡36^4(mod 45)
≡1296^2(mod 45)
≡36^2(mod 45)
≡1296(mod 45)
≡36(mod 45)【余36】
（2）用整除吧!
首先,3的100次方等于9的50次方,因而一定是9的倍数.
所以说,它除以45即使有余数也是9的倍数!
而3的幂的个位数变化规律为：
【3,9,7,1】,【3,9,7,1】,……
因而1的100次方的个位数为1.
也就是说,它除以45的余数只能为个位为6的9的倍数!那么只有36了!