Reduce power modulo a semiprime quickly by hand I worked through problem 7 in this GRE prep material (https://math.uchicago.edu/~min/GRE/files/week1.pdf), and I got the right answer, but I'm wondering if there is a more efficient way to do this, particularly considering that the GRE math subject test doesn't permit using a calculator. The question is to find the remainder upon dividing $ 13 ^{2019} $ by $95$. So we must solve for $x$ in $ 13^{2019} \equiv_{95} x.$ Since 95 factors into 5*19, I first found each of those residues.


$ 13^{2019} \equiv_{5} {{(13 \pmod 5})}^{2019 \pmod{\phi(5)}}\equiv_{5} 3^{2019 \pmod{4}}\equiv_{5} 3^3=27\equiv_{5}2.$
$ 13^{2019} \equiv_{19} {13}^{2019 \pmod{\phi(19)}}\equiv_{19} {13}^{2019 \pmod{18}}= 13^3\equiv_{19}(-6)^3=36*(-6)\equiv_{19}(-2)*(-6)\equiv_{19}12.$

Since $2 \equiv_5 12$, that means $13^{2019}$ is equivalent 12 with respect to each modulus, which means that $13^{2019} \equiv_{95} 12.$
Are there any other techniques I could have used to get the answer more quickly?
$\phi(95)=\phi(5) \cdot \phi(19) = 4 \cdot 18=72$.
$2019 \equiv 3 \pmod{72}, 13^{72} \equiv 1 \pmod{95}$, therefore
$$13^{2019} \equiv 13^3 \equiv 169 \cdot 13 \equiv  (-21) \cdot 13 \equiv 12 \pmod{95}$$
$\phi(95) = 95(1-\frac{1}{5})(1-\frac{1}{19})$ = 72
since 13 and 95 are coprime, $13^{72n}$ where n is a whole number will be 1 modulo 95.
$13^{2019} = 13^{2016+3} \equiv 13^{3} \equiv 2197 \equiv 12$ mod 95