Question: > 
> 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.

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$.
You can afford to work modulo $16=2^4$ and modulo $625=5^4$ separately. The basis $2016$ is a multiple of $16$ and therefore so are all its powers.

We also know that $2016\equiv141$ modulo $625.$

To take the $2016$-th power note that $141$ is invertible modulo $625$ (because it is relatively prime with $5$) and therefore its $500$-th power is equivalent to $1$ modulo $625$ (the multiplicative group modulo $625$ has order $5^3.(5-1)=500$). Thus we can limit ourselves to the $16$-th power.

To evaluate $141^{16}$ modulo $625$ notice that $141=5^3+16$ so

$$\eqalign{141^{16}=\sum\_{i=0}^{16}{16\choose i}5^{3i}16^{16-i}
&\equiv16^{16}+16.16^{15}.125\\
&\equiv16^{16}+1.125\\
16^{16}=(3.5+1)^{16}=\sum\_{i=0}^{16}{16\choose i}3^i5^i
&\equiv 1+16.3.5+8.15.3^2.5^2+8.5.14.3^3.5^3\\
&\equiv1+48.5+216.125\\
&\equiv1+48.5+1.125=366\\
141^{16}&\equiv366+125=491\\
}$$

This means we are looking for a number between $0$ and $9999$ that is a multiple of $16$ and that is $491$ more than a multiple of $625.$ Since $625\equiv1$ and $491\equiv11$ modulo 16 the solution should be $(16-11).625+491=3616.$