How to solve following problem? 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)?
 A: 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) $$
A: $$ 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)$$
