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

  • #1
326
42

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

Answers and Replies

  • #2
14,413
11,726
Start with ##(a^m)^{n'}##. Take the ##q## out of ##m## and put it in ##n'##.
 
  • #3
326
42
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##. []
 
  • Like
Likes fresh_42

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

Replies
9
Views
3K
  • Last Post
Replies
1
Views
2K
Replies
1
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
16K
  • Last Post
Replies
2
Views
6K
  • Last Post
Replies
8
Views
875
Replies
4
Views
1K
Replies
1
Views
470
  • Last Post
Replies
1
Views
544
Top