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?
 A: Your argument would work fine for finding the last two digits of $7^{89}$. But just because $7^4 = 2\,401$ ends in $01$ doesn't mean that $47^4$ will. (In fact, $47^4 = 4\,879\,681$.)
It takes a lot longer for the last digits two of $47^n$ to cycle. You'll at least be able to do calculations with smaller numbers if you think about powers of $47$ separately mod $25$ and mod $4$, then apply the Chinese remainder theorem.
Another approach is to try to compute the last two $47^{89}$ directly by using as few multiplications as possible. For example, if you get the last two digits of $47^{11}$, you can square them three times to get the last two digits of $47^{88}$, and multiply by $47$ again to get to $47^{89}$. (There might be faster ways, too; this is just the first I thought of.)
A: 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.
A: $(50-3)^2\equiv10-1\pmod{100}$
$\implies47^{4n+1}=47(47^2)^{2n}\equiv47(10-1)^{2n}$
Now $\displaystyle(10-1)^{2n}=(-1+10)^{2n}\equiv1-\binom{2n}110\pmod{100}\equiv1+80n$
Here $4n+1=89\iff n=?$
Can you take it from here?
A: \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.$
