Find the last two digits of $47^{89}$ Find the last two digits of the number $47^{89}$
I applied the concept of cyclicity
$47\cdot 47^{88}$
I basically divided the power by 4 and then calculated $7^4=2401$ and multplied it with 47 which gave me the answer $47$ but the actual answer is $67$. How?

Note that $\varphi(100)=40$ and that $47$ is coprime to $100$, so by Euler's theorem we have $47^{40} \equiv 1 \bmod{100}$, and so
$$47^{89} \equiv (47^{40})^2 \cdot 47^9 \equiv 1^2 \cdot 47^9 \equiv 47^9 \bmod{100}$$
Now $47^2 = 2209 \equiv 9 \bmod{100}$. Hence
$$47^8 \equiv (47^2)^4 \equiv 9^4 \equiv 81^2 \equiv 6561 \equiv 61 \bmod{100}$$
It follows that
$$47^{89} \equiv 47^9 \equiv 47^8 \cdot 47 \equiv 61 \cdot 47 = 2867 \equiv 67 \bmod{100}$$
This isn't the most elegant solution, but it can be done without dealing with numbers any longer than four digits, so it would be reasonable to be able to do it by hand.
