Ta tìm số dư khi chia 3^100 cho 1000
3^4 = 81 (modulo 1000)
3^5 = 3*81 = 243 (modulo 1000)
3^10 = 243^2 = 49 (modulo 1000)
3^20 = 49^2 = 401 (modulo 1000) *
3^40 = 401^2 = 801 (modulo 1000)
3^50 = 3^40*3^10 = 801*49 = 249 (modulo 1000)
3^100 = 249^2 = 1 (modulo 1000)
=> 3 chữ số...