This is a homework question.
I need to calculate 45 ^ 60 mod 61. I want to know about any fast method in order to get the result programmatically or manually, whichever is faster.
The result will be 1 due to Fermat's little theorem
if pis simple.
p
61 is a prime, so a p-1when divisible by p, gives 1 as the remainder.
a
p-1
However, if pnot simple, the usual trick is repeated.
45^60 = 2025^30 = (33*61 + 12)^30 = 12^30 = 144^15 = (2*61 + 22)^15 = 22^15 = 10648^5 = ( 174*61 + 34)^5 = 34^5 = 45435424 = 744843 * 61 + 1 = 1
Here equality means = (mod 61)
, .
p = 61 p-1 = 60.
,
45^2 = 2025 = 12 45^4 = 12^2 = 144 = 22 45^8 = 22^2 = 484 = 57 45^16 = 57^2 = 3249 = 16 45^32 = 16^2 = 256 = 12 45^60 = 45^(4+8+16+32) = 22 * 57 * 16 * 12 = 1
Always Wolfram Alpha : D
