Proofs and numbers
posted by yin on .
Use Fermat's Little Theorem to find the remainder on division 5^120 by 19.

According to Fermat's Little Theorem:
5^18 = 1 Mod 19
This means that in the exponent you can reduce Mod 18.
120 Mod 18 = 20*6 Mod 18 = 2*6 Mod 18 = 12 Mod 18
5^3 Mod 19 = 125 Mod 19 =
(20*6+5) Mod 19 = 6+5 = 11
5^6 Mod 19 = 11^2 = (6*20+1) Mod 19 = 7
5^12 Mod 19 = 7^2 Mod 19 = 49 Mod 19 = 11