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.
 A: Since $10000=2^4\times5^4$, we can use the Chinese Remainder Theorem after evaluating $5^{5555}$ modulo $2^4$ and modulo $5^4$.  The latter is easy:
$$5^{5555}\bmod 5^4=0\ .$$
For the former, start evaluating powers of $5$ modulo $2^4=16$: we have
$$5^1\equiv5\ ,\quad 5^2\equiv9\ ,\quad 5^3\equiv13\ ,\quad5^4\equiv 1\ .$$
It's not hard to see that $4$ is a factor of $5556$.  Hence
$$5^{5555}\equiv5^{4q+3}\equiv 1^q\times5^3\equiv13\ .$$
So if $x=5^{5555}$ we have
$$x\equiv13\pmod{2^4}\ ,\quad x\equiv0\pmod{5^4}$$
and the Chinese Remainder Theorem gives
$$x\equiv8125\pmod{10000}\ .$$
A: 
Find the remainder when $5^{5555}$ is divided by $10000$.

Also known as "find the last 4 digits of $5^{5555}$". Essentially this depends on the cycle length of 5 in $2^4$, which is $4$. So we're only interested in what $5555 \pmod 4$ is: $3$. In order to saturate the $4$-fold multiplicity of $5$ in $10000$, we'll look at $5^7 \pmod {10000}$ instead, which is our answer: $8125$ 
A: 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$.
A: Hint $\,\ 2^{\large 4}\mid 5^{\large 4}\!-1 = 25^{\large 2}\!-1 = 24\cdot 26,\,$ so $\ 10^{\large 4}\mid 5^{\large 4}(5^{\large 4}\!-1) = 5^{\large 8}-5^{\large 4}\ $ so
${\rm mod}\ 10^{\large 4}\!:\,\ 5^{\large 8} \equiv  5^{\large 4}\,\overset{\large \times 5^4}\Rightarrow\, 5^{12} \equiv 5^{\large 4}\overset{\large \times 5^4}\Rightarrow\, 5^{\large 16} \equiv 5^{\large 4}\,\ldots \Rightarrow\, 5^{\large 4N} \equiv 5^{\large 4} $
