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
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.
No comments:
Post a Comment