Order of a^m when gcd(m,n) = 1

[fishturtle1]

Homework Statement

At beginning of problem section: Let $\operatorname{ord}(a) = n$. (Not sure if that carries into this problem..)

Prove that if $a^m$ has order $n$ then $\gcd(m,n) = 1$. (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. )

Homework Equations

Order of $a$ is the least positive integer such that $a^{\operatorname{ord}(a)} = e$.

From a different problem: $\operatorname{ord}(a^m) \vert \operatorname{ord}(a)$.

Previous problem: if $\gcd(m,n) = 1$ then $\operatorname{ord}(a^m) = \operatorname{ord}(a) = n$.

The Attempt at a Solution

Suppose $\gcd(m,n) = q > 1$. Then there exists integers $m', n'$ such that $m = m'q$ and $n = n'q$. By definition of order, $(a^m)^n = (a^m)^{n'q} = (a^{mq})^{n'} = e$. Also $\gcd(m', n') = 1$.

I'm not sure how to get to $(a^m)^{n'} = e$..

 

[fresh_42]

Start with $(a^m)^{n'}$. Take the $q$ out of $m$ and put it in $n'$.

 

[fishturtle1]

Proof: We'll prove this by contrapositive. Suppose $\gcd(m,n) = d > 1$. Then $m = m'\cdot d$ and $n = n' \cdot d$ for integers $m', n'$. Observe, $(a^m)^{n'} = (a^{m'd})^{n'} = (a^{m'})^n = (a^n)^{m'} = e^{m'} = e$. So $(a^m)^{n'} = e$. Thus, $\operatorname{ord}(a^m) \le n' < n$.

We can conclude if $\operatorname{ord}(a^m) \ge n$ then $\gcd(m,n) = 1$.

Additionally, since $(a^m)^n = (a^n)^m = e^m = e$, it follows $\operatorname{ord}(a^m) \le n$. So we can be more specific and say if $\operatorname{ord}(a^m) = n$ then $\gcd(m,n) = 1$. []