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. 
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.
 A: Your idea is good, but you can't do $g^{\frac{1}{k}}$ in groups.

Let $d=\gcd(m,n)$ and write $m=m'd$, $n=n'd$. Then
$$
(a^m)^{n'}=(a^{m'd})^{n'}=a^{n'dm'}=(a^{n'd})^{m'}=(a^n)^{m'}=e^{m'}=e
$$
Since $n'\le n$ and $a^m$ is assumed to have order $n$, we conclude that $n'=n$, so $d=1$.
A: 10.G.2 from Pinter:

a ∈ G
ord(a) = n
Prove: If a^m has order n, then m and n are relatively prime.
(HINT: Assume m and n have a common factor q > 1, hence we can
  write m = m'q and n = n'q. Explain why (a^m)^n' = e, and proceed from
  there.)

(This is an extremely granular step-by-step transformation approach for folks who may be new to this material.)
We are given:
a ∈ G                   (1)

ord(a) = n              (2)

ord(a^m) = n            (3)

Let's assume m and n have a common factor q > 1. (4)
I.e. gcd(m,n) ≠ 1.
Thus we can write:
m = m' q                                (5)

n = n' q                                (6)
--------------------------------------------------------------------------------
n = n' q        Eq (6).

n' = n/q        Solve for n'.           (7)
--------------------------------------------------------------------------------
m = m' q        Eq (5).

q = m/m'        Solve for q.            (8)
--------------------------------------------------------------------------------
n' = n/q        Eq (7).

n' = n/(m/m')   Substitute (8).

n' = nm'/m                              (9)
--------------------------------------------------------------------------------

This is a long winded way of saying "take (5) and (6), isolate n' and eliminate q.
Let's start with:
a^m

Raise it to n':
(a^m)^n'

(a^m)^(nm'/m)       Substitute (9).

a^(m n m' / m)

a^(n m')            m cancels out.

(a^n)^m'

e^m'                By (2).

e

Thus we have:
(a^m)^n' = e                        (10)

(6) implies that:
n' < n                              (11)

(10) and (11) together imply that n is not the lowest number such that (a^m)^n = e.
This contradicts (3).
So our assumption (4) is false.
