Calculating AB mod C for any B
Find: 5117 mod 19
Step 1: Rewrite B into its binary form
117 = 1110101 = 1 2^6 +1 2^5 + 1 2^4 + 1 2^2 + 1*2^0
117 = 64 + 32 + 16 + 4 + 1
Step 2: Convert to Powers of 2 and find the mod
5117 mod 19 = (52^6 52^5 52^4 52^2 52^0)
51 mod 19 = 5
52 mod 19 = (55) mod 19 = 25 mod 19 = 6
54 mod 19 = (66) mod 19 = 36 mod 19 = 17
58 mod 19 = (1717) mod 19 = 289 mod 19 = 4
516 mod 19 = (44) mod 19 = 16 mod 19 = 16
532 mod 19 = (1616) mod 19 = 256 mod 19 = 9
564 mod 19 = (99) mod 19 = 81 mod 19 = 5
Step3: Combine the individual powers to find the final answer
5117 mod 19 = (564532 5165451 ) mod 19
= (564 mod 19 532 mod 19 516 mod 19 54 mod 19 51 mod 19 )mod 19
= 61200 mod 19
= 1
