Remainder when $5^{5555}$ is divided by $10000$. Find the remainder when $5^{5555}$ is divided by $10000$.
A step by step guide with explanation for a beginner student in modular arithmetic is needed.

Start by factoring $10000 = 10^4 = 2^4 \times 5^4$.
So we want to know the results mod $2^4$ and mod $5^4$.
The second is easiest: $5555 > 4$ so $5^{5555} \equiv 0 \mod 5^4$.
Now mod $2^4 = 16$: $\gcd(2^4, 5) = 1$ and $\phi(16) = 8$, so $5^8 \equiv 1 \mod 2^4$.  $5555 \equiv 3 \mod 8$, so $5^{5555} \equiv 5^3 \equiv 13 \mod 2^4$.
You want a number $x \in [0,1,\ldots, 9999]$ with $x \equiv 0 \mod 5^4$ and $x \equiv 13 \mod 2^4$.  The $0$ makes it especially easy.  You'll have
$x = 5^4 y$, and $5^4 \equiv 1 \mod 2^4$, so $y \equiv x \equiv 13 
\mod 2^4$.  You can take $y = 13$ and thus $x = 8125$.
