Find the last $4$ digits of $2016^{2016}$.
Technically I was able to solve this question by I used Wolfram Alpha and modular arithmetic so the worst I had to do was raise a $4$ digit number to the $9$th power. I would do $2016^2 \equiv 4256^2 \equiv \cdots$
and then continue using the prime factorization of $2016$. I am wondering if there is a better way to solve this.
Best Answer
$$\begin{align}(2000+16)^{2016}&\equiv 2016\cdot 2000\cdot 16^{2015} + 16^{2016}&\pmod{10000}\\ &\equiv 2000+16^{2016}&\pmod{10000} \end{align}$$
So you need to find the last four digits of $16^{2016}$ and add $2000$.
You can actually reduce the exponent modulo $500$, because $16^{2016}\equiv 16^{16}\pmod{625}$ and $16^{2016}\equiv 0\equiv 16^{16}\pmod{16}$.
So you need to compute $16^{16}\mod{10000}$. This can be done by repeated squaring:
$$16^2=256\\ 16^4=256^2\equiv 5536\pmod{10000}\\ 16^8\equiv 5536^2\equiv 7296\pmod{10000}\\ 16^{16}\equiv 7276^2\equiv 1616\pmod{10000}\\ $$
So the result is $2000+1616=3616$.