How do I find the remainder for the following?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

$19(2)\mid 19(18)\mid 19^{n+1}\!-19$
since: $\, a(a\!-\!1)\mid a(a^n-\,1)$

Answer 4

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}$