Remainder of $15^{81}$ divided by $13$ without using Fermat's Little theorem.

Question

I was requested to find the congruence of $15^{81}\mod{13}$ without using Fermat's theorem (since that is covered in the chapter that follows this exercise). Of course I know that by property $15^{81} \equiv 2^{81} \pmod{13}$, but how could I find what is the congruence of $2^{81}$ without using Fermat? Needless it is to say that an exhaustive iterative method would be extremely long.

Answer 1

$15\equiv2\bmod13$, so we have $$15^{81}\equiv2^{81}\bmod{13}$$$$\equiv512^9\equiv5^9\bmod{13}$$$$\equiv125^3\equiv8^3\bmod{13}$$$$\equiv512\equiv5\bmod13$$

Answer 2

We can for example use $15=3 \cdot 5$ and notice $3^3=27 \equiv 1 \bmod 13$, and $5^2=25 \equiv -1 \bmod 13$. So $$ 15^{81}=3^{81}5^{81}=(3^{3})^{27}(5^2)^{40}5\equiv 1^{27}(-1)^{40}5=5 \pmod{13}. $$