Find the remainder when $13^{13}$ is divided by $25$. Find the remainder when $13^{13}$ is divided by $25$.
Here is my attempt, which I think is too tedious:
Since $13^{2} \equiv 19 (\text{mod} \ 25),$ we have $13^{4} \equiv 19^{2} \equiv 11 (\text{mod} \ 25)$ and $13^{8} \equiv 121 \equiv 21 (\text{mod} \ 25).$
Finally, we have $13^{8+4} \equiv 13^{12} \equiv  21\times 11 \equiv 231 \equiv 6 (\text{mod} \ 25)$ and hence $13^{13} \equiv 3 (\text{mod} \ 25).$
Is there a less tedious way to find the remainder? Thank you.
 A: $13$ is coprime with $25$, so Euler-Fermat tells us that
$$
13^{\varphi(25)}\equiv1\pmod{25}
$$
Since $\varphi(25)=20$, this is not much of a help.
You can try with repeated squares: $13=1+4+8$; since
$$
13^2\equiv 19,\quad
13^4\equiv 19^2\equiv11\quad
13^8\equiv 11^2\equiv21
$$
we get
$$
13^{13}\equiv 13\cdot 11\cdot 21\equiv3\pmod{25}
$$
which actually is what you did. I don't think there's much easier methods.
A: $\!\bmod 25\!:\ 13\equiv \overbrace{2^{\large -1}\!\equiv 3^{\large -3}}^{\Large 2\ \, \equiv\,\ 3^{\LARGE 3}}$ $\Rightarrow 13^{\large 13}\!\equiv 3^{\large -39}\!\equiv 3,\ $ by $\ 3^{\large 40}\!\equiv\!\!\! \overbrace{(3^{\large \color{#c00}{20}})^{\large 2}\!\equiv 1}^{\large\quad\ \  \color{#c00}{20}\ =\ \phi(25)}$ 
A: Not really, you could only use this $$19\equiv -6\pmod {25}$$ and $$121\equiv -4\pmod {25}$$
That would perhaps save you some time.

By Euler theorem you could also see that
$$
13^{20}\equiv1\pmod{25} \implies 13^{10}\equiv \pm1\pmod{25}
$$
so 
A: We have


*

*$2\cdot 13 = 26 \equiv 1 \mod 25$

*$\Rightarrow 13^{13} \cdot \color{blue}{2^{13}} \equiv 1 \mod 25$

*$\color{blue}{2^{13}} \equiv 2^{10}\cdot 2^3 \equiv -8 \color{blue}{\equiv 17 \mod 25}$
$$\Rightarrow \boxed{13^{13} \equiv 17^{-1} \equiv 3 \mod 25}$$
