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

• fishturtle1
In summary, we need to prove that if the order of a given element raised to a power is the same as the order of the element, then the greatest common divisor of the power and the order is equal to 1. This can be shown by assuming that the power and the order have a common factor greater than 1, and using the properties of order to arrive at a contradiction. From this, we can also conclude that if the order of the element raised to the power is the same as the order of the element, then the greatest common divisor of the power and the order must also be equal to 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##..

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

## What is the purpose of studying the order of a^m when gcd(m,n) = 1?

The order of a^m when gcd(m,n) = 1 is a fundamental concept in abstract algebra that helps us understand the behavior of elements in a group. It also has important applications in cryptography and number theory.

## How is the order of a^m related to the concept of cyclic groups?

In a cyclic group, the order of an element is equal to the order of the entire group. Therefore, the order of a^m when gcd(m,n) = 1 will be the same as the order of the group.

## Can the order of a^m be larger than n when gcd(m,n) = 1?

Yes, the order of a^m can be larger than n when gcd(m,n) = 1. This happens when m and n are not relatively prime. For example, if m = n, then the order of a^m will be n instead of 1.

## How can the order of a^m be used to find the inverse of a modulo n?

When gcd(m,n) = 1, the order of a^m is equal to the order of a modulo n. This means that a^m is congruent to 1 modulo n. Therefore, the inverse of a modulo n can be found by raising a^m-1 to the power of m.

## Is there a formula for calculating the order of a^m when gcd(m,n) = 1?

Yes, there is a formula for calculating the order of a^m when gcd(m,n) = 1. It is given by φ(n)/gcd(φ(n),m), where φ(n) is Euler's totient function. This formula is useful when n is a large number.

• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
11
Views
1K
• Calculus and Beyond Homework Help
Replies
1
Views
859
• Calculus and Beyond Homework Help
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
12
Views
1K
• Precalculus Mathematics Homework Help
Replies
2
Views
1K
• Calculus and Beyond Homework Help
Replies
5
Views
2K
• Precalculus Mathematics Homework Help
Replies
3
Views
967
• Linear and Abstract Algebra
Replies
3
Views
2K