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$.
Since $2016$ is a multiple of $16$, we shall look at the $2016^ {2016}$ modular $625$. 

Well, following from [Euler`s Theorem](https://en.wikipedia.org/wiki/Euler%27s_theorem), $2016^{2016} \equiv 2016^{16} \pmod {625}$. Note that $2016^ {15}=(2000+16)^ {15} \equiv16^ {15} \pmod {625}$, following from the [Binomial theorem](https://en.wikipedia.org/wiki/Binomial_theorem). However, $16^ {15}=2^ {60} \equiv 399^6 \equiv (400-1)^6$, which calculated through the binomial theorem, is $101$. This gives us that $2016^ {16} \equiv 101\*2016 \equiv 491 \pmod {625}$. 

Combining this with the upper result gives us $3616$.