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?

\begin{align}
47^2 &= 40^2 + 2\times 40\times 7 + 7^2 \equiv 9 \pmod{100},\\
47^4 &\equiv 9^2 \equiv 81 \pmod{100}, \\
47^8 &\equiv 81^2 \equiv 61 \pmod{100}, \\
47^{16} &\equiv 61^2 \equiv 21 \pmod{100}. \\
\end{align}
At this point, if we recognize how convenient the results 
$47^4 \equiv 81 \pmod{100}$ and $47^{16} \equiv 21 \pmod{100}$ are,
we might continue with
\begin{align}
47^{20} &= 47^{16} \times 47^4 \equiv 21\times 81 \equiv 1 \pmod{100}, \\
46^{80} &\equiv 1 \pmod{100}, \\
47^9 &\equiv 61 \times 47 \equiv 67 \pmod{100}, \\
47^{89} &= 47^{80} \times 47^9 \equiv 67 \pmod{100}. \\
\end{align}
If we did not notice that $47^{20}\equiv 1 \pmod{100},$ however, we
could continue squaring to find $47^{32} \equiv 41 \pmod{100}$
and $47^{64} \equiv 81 \pmod{100},$
and then use the fact that 
$47^{89} = 47^{64} \times 47^{16} \times 47^{8} \times 47.$
