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?
 A: 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.
A: Precisely, Euler's totient function comes to be very handy for such problems. Euler's theorem states that if gdc$(a,m)=1$, then $a^{\phi(m)} \equiv 1 \pmod{m}$. In your case, since gdc$(19,38) \neq 1$, the fact that $19^2 \equiv 19 \pmod{38}$ is crucial, and from that one gets $19^n \equiv 19 \pmod{38}$, for every $n \in \mathbb{N}$. For instance, if you want to calculate the remainder of $17^{38}$ when divided by 38, first observe that gdc$(17,38) = 1$ (here we can use Euler's theorem), and that $\phi(38)=18$. So, since $38= 2 \times 18 +2$, we have
$$
17^{38}=17^{2 \times 18 +2}=(17^{18})^217^2 \equiv 17^2 \equiv 23 \pmod{38}.
$$
That's the "canonical" way.
A: $19(2)\mid 19(18)\mid 19^{n+1}\!-19$
since: $\, a(a\!-\!1)\mid a(a^n-\,1)$
A: For $19^{a+1}\pmod{38},$
let us find $19^a\pmod{\dfrac{38}{19}}$
As $19\equiv1\pmod2$
$19^a\equiv1^a\equiv1\pmod2$ for integer $a\ge0$
$\implies19^{a+1}\equiv1\cdot19\pmod{2\cdot19}$
See also : How to find last two digits of $2^{2016}$
