<s>[INST] 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.
 [/INST] $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.
</s>