09/10/17 06:41:39
>>512-513
3^100 = 9^50
= (10-1)^50
≡ Ｃ[50,2] 10^2 - Ｃ[50,1] 10^1 + Ｃ[50,0] 10^0 (←2項展開)
= 1225×100 - 50×10 + 1
≡ 5×100 - 50×10 + 1
= 1, (mod 1000)
だから、下二桁を考えれば十分。
3^4798 ≡ {3^(-1)}^2 = (-333)^2 ≡ -111, (mod 1000)
3^4567 ≡ 3^67 ≡ 587 (mod 1000)