Let $a$ be an element of order $n$ in a group $G$. If $m$ and $n$ are relatively prime, then $a^m$ has order $n$. 
Let $a$ be an element of order $n$ in a group $G$.
If $m$ and $n$ are relatively prime, then $a^m$ has order $n$.

Assume $m$ and $n$ are relatively prime, and that $a^m$ does not have order $n$. Say it has order $k$, so that $(a^m)^k=e$.
Since the order of $a$ is $n$, $$e=a^n=(a^m)^k$$
So, $mk \equiv 0 \pmod n$, and therefore $n \mid mk$
Since $n$ is a factor of $mk$, and since $n$ and $m$ are relatively prime, $n$ must be a factor of $k$ only.
From the premise of my proof, I should be coming up with some sort of contradiction involving: $m$ and $n$ are not relatively prime; but I can't come up with this.
 A: Hint: You have $n$ is a factor of $k$. Then, $n \mid k \Rightarrow k \geq n$. Is there a contradiction to be found here?
A: Write $b=a^m$ with order $k$.
First note $b^n=a^{mn}=(a^n)^m=e$, so $k|n$.
On the other hand, $e=b^k=a^{mk}$, so $n|mk$. But since $m,n$ are relatively prime, we have $n|k$.
Hence $k=n$
A: This is 10.G.1 from Pinter:

If m and n are relatively prime then a^m has order n.
(HINT: If a^(mk) = e, use 10.T5 and explain why n must be a factor
  of k.)

He suggests that we use 10.T5:

Suppose an element a in a group has order n. 
Then a^t = e iff t is a multiple of n ("t is a multiple of n"
  means that t = nq for some integer q).

The proof:
ord(a) = n                  (1)

gcd(m,n) = 1                (5)

(a^m)^n
(a^n)^m
e^m
e

Thus:
(a^m)^n = e

If n is the lowest number such that the above is true, then n is the order of a^m.
Let's check to see if there is a lower number.
Suppose there is a number k such that:
k < n                       (3)

(a^m)^k = e

Then we have:
a^(mk) = e                  (2)

By 10.T5 with (1) and (2):
n | mk

Due to (5), n does not divide m. So it must divide k:
n | k                   (4)

(4) contradicts (3) therefore there is no such number k.
Therefore n is the minimum value such that:
(a^m)^n = e

I.e.
ord(a^m) = e

