Proof relating to the order of $a \mod n$?

Question

The proof required is to show that $\operatorname{ord}_n(a^j) \mid\operatorname{ord}_n(a)$, for any positive integer $j$. I have considered using a proof by contradiction, but am having trouble going from there. Thanks

Answer 1

$(a^j)^m=(a^m)^j=1^j=1$ and so ord $a^j$ must divide $m=$ ord $ a$.

Answer 2

Let $m=\mathcal O(a)$, $d=\gcd(j,m)$, $n=m/d$. Then $a^{jn}=a^{jm/d}=(a^m)^{j/d}=1$.

Suppose now that $a^{jk}=1$. Then, $m|jk$ and $n|(j/d)k$. Since $n$ and $j/d$ are coprime, $n|k$. This proves that $\mathcal O(a^j)=n$, which clearly divides $m$.

Remark: As @lhf has shown, the proof that you have asked for is much simpler, but I wanted to actually compute $\mathcal O(a^j)$.