How to solve following problem?

Question

I know it might have something to do with modular exponentiation, but after extensive search and reading, I am completely dumbfounded.

$$\text {Let}\; N = 12 = 2^2 + 2^3$$ Given that $M^2 \equiv 51$ (mod 59), What is $M^{12}$(mod 59)?

Answer 1

$$ M^2\equiv 51 (\mod 59) \implies M^2\equiv -8 (\mod 59)$$

$$ M^4\equiv 64 (\mod 59) \implies M^4\equiv 5 (\mod 59)$$

$$ M^8\equiv 25 (\mod 59) \implies M^{12}\equiv 5(25) (\mod 59)$$

$$ M^{12}\equiv 125 (\mod 59) \implies M^{12}\equiv 7 (\mod 59)$$

Answer 2

An explanation of the accepted answer above for anyone else coming here from WGU.

Given that we know:

$$ [(x\ mod\ n)(y\ mod\ n)]\ mod\ n = [x·y]\ mod\ n $$

and basic exponential power rules:

$$ M^{12} \equiv (M^8)(M^4) \equiv (((M^2)^2)^2)((M^2)^2) $$

we can use $ M^2 $ to find $ M^{12} $:

$$ M^4 \equiv (M^2)^2 \equiv (M^2)(M^2) \equiv [(51\ mod\ 59)(51\ mod\ 59)] \equiv 51^2(mod\ 59) $$

Because $ 51^2 $ is already quite large to compute, we know that via modulo congruence that $ -8 \equiv 51(mod\ 59) $, hence:

$$ M^4 \equiv 51^2(mod\ 59) \equiv (-8)^2(mod\ 59) \equiv 64(mod\ 59) \equiv 5(mod\ 59) $$

Repeat to get us to $ M^8 $ (leaving out the expansion and then later simplification of the exponents):

$$ M^8 \equiv (M^4)^2 \equiv 5^2(mod\ 59) \equiv 25(mod\ 59) $$

Lastly, we can use previously computed values to find $ M^{12} $:

$$ M^{12} \equiv (M^4)(M^8) \equiv [(5\ mod\ 59)(25\ mod\ 59)] \equiv 5(25)(mod\ 59) \equiv 125(mod\ 59) \equiv 7(mod\ 59) $$