Does GCD Condition Prove Multiplicative Order?

  • Thread starter HF08
  • Start date
In summary: Clearly, number 2 is just saying that the order of ab is k. I think I can show (ab)^k=a^k b^k=1 easily. So I get x|k and y|k....That's correct.
  • #1
HF08
39
0
Please help me prove this. I worked hard to make my notation somewhat easy to follow:

If gcd ( ord_n(a) , ord_n(b) ) = 1 , then ord_n(a*b) = ord_n(a) * ord_n(b)


Attempted proof:

I can't see how to use the gcd condition. Which is bad news. I do realize the following.
Let k1 = ord_n(a) and k2 = ord_n(b). Hence, a^k1 == 1 (mod n) and b^k2 == 1 (mod n).
Thus, (a^k1)*(b^k2) = = 1 (mod n).

I am very stuck. Can you please help me?

HFO8
 
Physics news on Phys.org
  • #2
If you are to show that it is multiplicative its only necessary to show that if (a,b)=1 then ord_n(a*b)=ord_n(a)*ord_n(b), not that if (ord_n(a),ord_n(b)) then ord_n(a*b)=ord_n(a)*ord_n(b).

Or am I terribly mistaken?
 
  • #3
Thanks for your quick reply.

*-<|:-D=<-< said:
If you are to show that it is multiplicative its only necessary to show that if (a,b)=1 then ord_n(a*b)=ord_n(a)*ord_n(b), not that if (ord_n(a),ord_n(b)) then ord_n(a*b)=ord_n(a)*ord_n(b).

Or am I terribly mistaken?

Well, the way the problem is written is written with gcd ( ord_n(a), ord_n(b) ) = 1.
So, does this condition imply gcd (a, b) = 1? Please tell me how to solve this with just
(a , b) = 1. Perhaps there is something analogously that may be done.

Thanks,
HF08
 
  • #4
Let's just look at one element, a. Suppose a has order k. Now, [itex]a^n=1[/itex] if and only if...what? What must be true about k and n for [itex]a^n=1[/itex]? Now use that to look at when [itex](ab)^n=1[/itex].
 
  • #5
Thanks for the reply and some comments of my own...

abelian jeff said:
Let's just look at one element, a. Suppose a has order k. Now, [itex]a^n=1[/itex] if and only if...what? What must be true about k and n for [itex]a^n=1[/itex]? Now use that to look at when [itex](ab)^n=1[/itex].

I found your post confusing. This is what I have been doing. Staying true to the notation
in my original problem.

Part I.
Let x = ord_n(a). So a^x = = 1 mod n iff gcd(a,n) = 1

Now, let y = ord_n(b). (a^y)x = = 1 mod n. Hence, a^xy = = 1 mod n.

Similarily, b^xy = = 1 (mod n).

Part II.

By Part I, we know (ab)^xy ==1 (mod n). So we know that ord_n(ab) | xy.

So, how can I show that ord_n(a)| ord_n(ab) and ord_n(b) | ord_n(ab)? If so,
I think I can then claim the conclusion.

I don't know what you were trying to suggest. If you have an easier way to prove this problem, please let me know.

HFO8
 
  • #6
Perhaps the fact that I used "n" in my post was confusing. The "n" that I was using was not the same "n" that you are modding out by.

I'll retype my idea. I'm just going to talk about the order of an element, not "ord_n(a)" since this is cumbersome, and we both know that we're working mod n.

Let the order of a = x and let the order of b =y.

Now, if we raise a to some power, say k, and this happens to be the identity

[itex]a^k = 1[/itex]

then what can we say about the relationship between x (which is the order of a) and k?

Similarly, if we raise b to some power k, and this happens to be the identity

[itex]b^k = 1[/itex]

then what can we say about the relationship between y (which is the order of b) and k?

If this is confusing, just plug in real numbers.

The point I'm trying to make is that you can't raise [itex]a[/itex] to just any number and have it equal the identity. If [itex]a^k = 1[/itex] then there is something very specific you can say about [itex]gcd(x,k)[/itex].

Once you figure that out, take a look at

[itex](ab)^k = 1[/itex]

and use what you've just discovered to finish your problem.
 
  • #7
abelian jeff said:
then what can we say about the relationship between x (which is the order of a) and k?

gcd(x, k ) = x, since x is the smallest integer such that a^x = = 1 mod n

Right? Am I getting warmer? I have been stating x | k ?
 
Last edited:
  • #8
Exactly! We know that x divides k in that case.

So now look at this:

[itex](ab)^k=a^k b^k=1[/itex] (since [itex]\mathbb{Z}/n\mathbb{Z}[/itex] is abelian)

and use the facts that:

1) [itex]gcd(x,y)=1[/itex]

and

2) the order of [itex]ab[/itex] is the least positive integer such that [itex](ab)^k=1[/itex]

to finish the problem.
 
  • #9
abelian jeff said:
Exactly! We know that x divides k in that case.

So now look at this:

[itex](ab)^k=a^k b^k=1[/itex] (since [itex]\mathbb{Z}/n\mathbb{Z}[/itex] is abelian)

and use the facts that:

1) [itex]gcd(x,y)=1[/itex]

and

2) the order of [itex]ab[/itex] is the least positive integer such that [itex](ab)^k=1[/itex]

to finish the problem.


So how can I justify just saying [itex]a^k=1[/itex] and [itex]b^k=1[/itex] for some k? I doubt I can just say, suppose there is some k>x and k>y such that...

Clearly, number 2 is just saying that the order of ab is k. I think I can show [itex](ab)^k=a^k b^k=1[/itex] easily. So I get x|k and y|k. Since gcd(x,y) = 1, then xy|k. Right?

So, how can I argue that k is ord ab? I thought I was close, but this is going in a direction I wasn't thinking about.


Summary:
How can I just state some k, like we discussed?
Is the goal to show xy|k?
If so, how can I argue k is the ord of ab?


My other post has proven k|xy. So if we know xy|k and k|xy, then we are done.

Thanks,
HF08
 
  • #10
HF08 said:
So how can I justify just saying [itex]a^k=1[/itex] and [itex]b^k=1[/itex] for some k? I doubt I can just say, suppose there is some k>x and k>y such that...

Clearly, number 2 is just saying that the order of ab is k. I think I can show [itex](ab)^k=a^k b^k=1[/itex] easily. So I get x|k and y|k. Since gcd(x,y) = 1, then xy|k. Right?

So, how can I argue that k is ord ab? I thought I was close, but this is going in a direction I wasn't thinking about.


Summary:
How can I just state some k, like we discussed?
Is the goal to show xy|k?
If so, how can I argue k is the ord of ab?


My other post has proven k|xy. So if we know xy|k and k|xy, then we are done.

Thanks,
HF08

Hi HF08,

I think you're getting too caught up in the notation. My k's, etc. are just letters I'm using to illustrate the main ideas.

Look, this is what you have shown:

If x is the order of a, and [itex]a^k=1[/itex], then x divides k.

Similarly,

If y is the order of b, and [itex]a^j=1[/itex], then y divides j.

Those numbers, k and j, are just there to illustrate the idea. Don't get caught up on what they are; they are simply multiples of x and y, respectively, and they are only there to make a point.

Now, we want to find the order of ab, correct? That was the original problem. We want to show that the order of ab is xy.

Well, let's take a look at ab. Let us say that the order of ab = k. Then we have

[itex](ab)^k=a^k b^k =1 [/itex].

Well then, this implies that x divides k. It also implies that y divides k. We know that [itex]gcd(x,y)=1[/itex]. And finally, we know that k is the LEAST number positive integer such that the equation above holds. We have all of the pieces of the puzzle, now we just need to put them together to show that k=xy.
 
  • #11
Thanks. Got it. (Almost got it?)

abelian jeff said:
Hi HF08,

Well then, this implies that x divides k. It also implies that y divides k. We know that [itex]gcd(x,y)=1[/itex]. And finally, we know that k is the LEAST number positive integer such that the equation above holds. We have all of the pieces of the puzzle, now we just need to put them together to show that k=xy.

Yes, you are correct. The notation was getting to me. I believe I am more clear on your
presentation and comments now. Thank you.

We know gcd(x,y) = 1 and x|k and y|k implies xy|k. Since ab^xy = 1, then k|xy.
Hence, k= xy.

Note:
(a^y)^x = 1
(b^x)^y = 1
Hence, ab^(xy) = 1

If you are thinking of an easier way. Please let me know. This is the idea I think your giving me.

HF08
 
Last edited:
  • #12
Great! You're finished! :smile:

As a bonus, you can easily adjust the argument to see that, in general, if x is the order of a, and y is the order of b, the order of (ab) is actually lcm(x,y). Of course, when gcd(x,y)=1, we have lcm(x,y)=xy, hence what you just showed.
 
  • #13
Thanks

abelian jeff said:
Great! You're finished! :smile:

As a bonus, you can easily adjust the argument to see that, in general, if x is the order of a, and y is the order of b, the order of (ab) is actually lcm(x,y). Of course, when gcd(x,y)=1, we have lcm(x,y)=xy, hence what you just showed.


Thank you very much for your help. I wonder if your interesting observation may give
us an easier proof.

lcm(x,y) = x*y/gcd(x,y) = x*y.

I think this is the last proof of that. I guess we could call that a lemma or corollary? Seems to me something easier to prove after we have shown ord ab = ord a * ord b.

Thanks again! I may have another number theory question tonight, but you really helped me a lot today. Thanks,
HF08
 
  • #14
One more question

abelian jeff said:
Hi HF08,
[itex](ab)^k=a^k b^k =1 [/itex].

Well then, this implies that x divides k. It also implies that y divides k.


I was trying to show this part rigorously. Do you have any ideas on how I might do this?
I agree it is true, but I am wondering if I should shore it up exactly.
 

FAQ: Does GCD Condition Prove Multiplicative Order?

What is the definition of multiplicative order?

The multiplicative order of an element a in a finite group G is the smallest positive integer n such that a^n = e, where e is the identity element of G.

How do you prove that the multiplicative order is multiplicative?

To prove that the multiplicative order is multiplicative, we need to show that for any two elements a and b in a finite group G, the multiplicative order of their product ab is equal to the least common multiple of their individual multiplicative orders.

Can you provide an example of how to show multiplicative order is multiplicative?

Let's take the group Z/12Z under addition, and consider the elements 2 and 3. The multiplicative order of 2 is 6, and the multiplicative order of 3 is 4. The product of 2 and 3 is 6, and the least common multiple of 6 and 4 is 12, which is also the multiplicative order of 2*3=6. Therefore, the multiplicative order is multiplicative in this example.

Is the multiplicative order always multiplicative in any finite group?

Yes, the multiplicative order is always multiplicative in any finite group. This is a fundamental property of finite groups and is proven in abstract algebra.

Why is it important to prove that the multiplicative order is multiplicative?

Proving that the multiplicative order is multiplicative is important because it allows us to simplify calculations involving powers of elements in finite groups. It also helps us better understand the structure and properties of finite groups.

Similar threads

Replies
3
Views
2K
Replies
17
Views
2K
Replies
1
Views
2K
Replies
19
Views
2K
Replies
5
Views
2K
Replies
59
Views
13K
Replies
4
Views
3K
Back
Top