Too many 85's

Relevant wiki: Euler's Theorem

Let $N$ be the number given in this problem. We are required to find $N \bmod 1000$ . Since $\gcd (85,1000) \ne 1$ , we have consider the factors 8 and 125 separately using Chinese remainder theorem .

We note that $N \equiv 0 \text{ (mod 125)}$ $\implies N \equiv 125n$ . Now, we have:

$\begin{aligned} N & \equiv 85^{\color{#3D99F6}85^a \bmod \phi(8)} \text{ (mod 8)} & \small \color{#3D99F6} \text{Since }\gcd(85,8) = 1 \text{, Euler's theorem applies.} \\ & \equiv 85^{\color{#3D99F6}85^a \bmod 4} \text{ (mod 8)} & \small \color{#3D99F6} \text{Euler's totient function }\phi (8) = 4 \\ & \equiv 85^1 \equiv 5 \text{ (mod 8)} \\ \implies 125n & \equiv 5 \text{ (mod 8)} \\ n & \equiv 1 \\ \implies N & \equiv \boxed{125} \text{ (mod 1000)} \end{aligned}$