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

## 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
Mentor
2021 Award
Start with ##(a^m)^{n'}##. Take the ##q## out of ##m## and put it in ##n'##.

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##. []

• fresh_42