Same Old Question!

Let $N=2016^{2016}$ . We need to find $A = N \bmod 10000$ . Since $\gcd (2016, 10000) \ne 1$ , we consider the factors of $2^4 = 16$ and $5^4 = 625$ separately using Chinese remainder theorem .

Factor 16: $N \equiv 0 \text{ (mod 16)}$ .

Factor 625: Since $\gcd (2016, 625) = 1$ , we can apply Euler's theorem and note that the Euler's totient function $\phi (625) = 500$ .

$\begin{aligned} N & \equiv 2016^{2016 \bmod \phi(625)} \text{ (mod 625)} \\ & \equiv 2016^{2016 \bmod 500} \text{ (mod 625)} \\ & \equiv 2016^{16} \text{ (mod 625)} \\ & \equiv (2025-9)^{16} \text{ (mod 625)} \\ & \equiv \left(-16\cdot 2025\cdot 9^{15} + 9^{16}\right) \text{ (mod 625)} \\ & \equiv \left(-16\cdot 225 \cdot 9^{16} + 9^{16}\right) \text{ (mod 625)} \\ & \equiv \left(-3599\cdot 9^{16}\right) \text{ (mod 625)} \\ & \equiv -474(10-1)^{16} \text{ (mod 625)} \\ & \equiv 151\left(\frac {15\cdot 16}2 \cdot 10^2 -16\cdot 10 + 1\right) \text{ (mod 625)} \\ & \equiv 151\left(12000 -160 + 1\right) \text{ (mod 625)} \\ & \equiv 151\left(125 -160 + 1\right) \text{ (mod 625)} \\ & \equiv 151\left(-34\right) \text{ (mod 625)} \\ & \equiv -5134 \text{ (mod 625)} \\ & \equiv -134 \text{ (mod 625)} \\ & \equiv 491 \text{ (mod 625)} \end{aligned}$

This implies that $N \equiv 625n + 491$ , where $n$ is a integer, and

$\begin{aligned} 625n + 491 & \equiv 0 \text{ (mod 16)} \\ n + 11 & \equiv 0 \text{ (mod 16)} \\ \implies n & \equiv 5 \\ N & \equiv 625\cdot 5+11 \equiv 3616 \text{ (mod 10000)} \end{aligned}$

Therefore, $A-1600 = 3616-1600 = \boxed{2016}$ .