Does GCD Condition Prove Multiplicative Order?

[HF08]

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

 

[Santa1]

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?

 

[HF08]

Thanks for your quick reply.

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

 

[abelian jeff]

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

 

[HF08]

Thanks for the reply and some comments of my own...

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

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

 

[abelian jeff]

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

$a^k = 1$

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

$b^k = 1$

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 $a$ to just any number and have it equal the identity. If $a^k = 1$ then there is something very specific you can say about $gcd(x,k)$.

Once you figure that out, take a look at

$(ab)^k = 1$

and use what you've just discovered to finish your problem.

 

[HF08]

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 ?

 

[abelian jeff]

Exactly! We know that x divides k in that case.

So now look at this:

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

and use the facts that:

1) $gcd(x,y)=1$

and

2) the order of $ab$ is the least positive integer such that $(ab)^k=1$

to finish the problem.

 

[HF08]

Exactly! We know that x divides k in that case.

So now look at this:

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

and use the facts that:

1) $gcd(x,y)=1$

and

2) the order of $ab$ is the least positive integer such that $(ab)^k=1$

to finish the problem.

So how can I justify just saying $a^k=1$ and $b^k=1$ 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 $(ab)^k=a^k b^k=1$ 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

 

[abelian jeff]

So how can I justify just saying $a^k=1$ and $b^k=1$ 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 $(ab)^k=a^k b^k=1$ 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 $a^k=1$, then x divides k.

Similarly,

If y is the order of b, and $a^j=1$, 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

$(ab)^k=a^k b^k =1$.

Well then, this implies that x divides k. It also implies that y divides k. We know that $gcd(x,y)=1$. 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.

 

[HF08]

Thanks. Got it. (Almost got it?)

Hi HF08,

Well then, this implies that x divides k. It also implies that y divides k. We know that $gcd(x,y)=1$. 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

 

[abelian jeff]

Great! You're finished!

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.

 

[HF08]

Thanks

Great! You're finished!

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

 

[HF08]

One more question

Hi HF08,
$(ab)^k=a^k b^k =1$.

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.