Let $a$ be an element of order $n$ in a group $G$.
If $a^m$ has order $n$, then $m$ and $n$ are relatively prime.
Assume $a^m$ has order $n$ and, $m$ and $n$ are not relatively prime. Then $m$ and $n$ have a common factor, say $q$. So, $m=m'q$ and $n=n'q$. So,
$$(a^m)^{n'}=(a^m)^\frac nq= (a^{mn})^\frac 1q= e^\frac 1q=e$$
So, $(a^m)^\frac nq=(a^m)^n=e$.
Since $a^m$ has order $n$: $e \neq (a^m)^\frac nq = (a^m)^n$. Contradiction.