Calculating pow(45,60) mod 61

This is a homework question.

I need to calculate 45^60 mod 61. I want to know of any fast method to get the result either programma开发者_如何学Gotically or manually whichever is faster.

The result would be 1 because of Fermat's little theorem

if p is prime.

61 is a prime number so ap-1 when divided by p would give 1 as the remainder.

However if p is non-prime the usual trick is repeated-squaring.

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)

I would say your best bet would be to use Fermat's Little Theorem.

Fermat's Little Theorem

where p = 61 and p-1 = 60.

Hope that helps

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

Wolfram Alpha

Always have Wolfram Alpha at hand :D