How do I find the remainder for the following? I know this is a very typical question for modular arithmetic but still I haven't found a comprehensive explanation for this question, so I'm posting it here. So here goes:
I need to find the remainder when $19^{38}$ is divided by $38$.
Here is my attempt:-
$$19\equiv 19\pmod {38}$$
$$19^2\equiv 19^2\pmod {38} \implies 19^2\equiv 19\pmod {38}$$
$$\implies (19^2)^2\equiv 19^2\pmod {38} $$
$$\implies 19^4\equiv 19\pmod {38}$$
$$\implies 19^8\equiv 19\pmod {38}$$
$$\implies 19^{16}\equiv 19\pmod {38}$$
$$\implies 19^{32}\equiv 19\pmod {38}$$
And carrying on I do get the answer that $$19^{38}\equiv 19\pmod {38}$$
But this seems a very cumbersome task, for higher powers it may be hard, or if 19 would not have been a factor of 38, then probably I wouldn't have been able to develop the pattern. Is there an easier and more methodical way to solve this using number theory/modular arithemtic?
I think I may have seen a solution involving Euler's Totient Function, but it was a while ago and I simply can't seem to relate it with this question and cant remember what the solution was. Can that be used to simplify this question?

Since $19^{38} - 19$ is divisible by both 2 and 19, it is divisible by 38.  Therefore,
$$19^{38} \equiv 19 \pmod{38}.$$
Euler's Theorem can't be applied here, since $\gcd(19,38)$ is not equal to 1.  But the fact that 19 divides 38 actually makes the calculation much easier.
