Order of Element: Prove o(ab) = hk

[annoymage]

Homework Statement

Let gcd(h,k)=1, o(a)=h, o(b)=k, show that o(ab)=hk

Homework Equations

o(a)= order of a modulo n

o(a)=k iff k is smallest integer,a^k=1 mod n

The Attempt at a Solution

to prove o(ab) l hk, no problem, just need to show (ab)^{hk}=1 mod n

and to prove hk l o(ab), use division algorithm

let, hk=p*o(ab)+q , 0\leq q<p

it can be shown that (ab)^q=1 mod n, this will imply q=0, so o(ab) l hk

and i really think i didn't make any mistake, but i didn't use that gcd(h,k)=1.
can help me anywhere i wrong? or is this gcd(h,k)=1 is unnecessary?

 

[jbunniii]

it can be shown that (ab)^q=1 mod n, this will imply q=0, so o(ab) l hk

I don't think this is correct. If it can be shown, then please show it.

It's simple to show that o(ab) | hk. It suffices to show that

(ab)^{hk} = 1

But

(ab)^{hk} = a^{hk} b^{hk} = (a^h)^k (b^k)^h = (1)(1) = 1

However, this isn't enough to imply that o(ab) = hk. For that, you will need to use the fact that gcd(h,k) = 1.

 

[jbunniii]

P.S. You didn't specify what group or ring or field you are working in. I infer that a and b are elements of \mathbb{Z}/(n) (integers modulo n). However, you did not mention whether n is prime. If not, then be aware that not every element necessarily has an order. For example, in \mathbb{Z}/(4), consider the element a = 2. There is no k for which 2^k = 1 (\mod 4), so w doesn't have an order in \mathbb{Z}/(4).

So if n is not necessarily prime, you need to do a bit more work to justify whether o(ab) is even defined.

 

[annoymage]

ahh, sorry i was blatantly showing o(ab) l hk twice, that was soo stupid, i have to show hk l o(ab)

i think i get it already but something not sure, so let o(ab)=r

and i know o(a^k)=h and o(b^h)=k since (h,k)=1

this one I am not sure, r l hk then let e be such that re=hk
so then (a^k)^r=(a^k)^{hk/e}=1^{k/e}=1mod n, so is it ok? because I am not sure power of a fraction is really define?

if it is ok then, h l r, similar argument to get k l r, so hk l r, since (h,k)=1

and btw, hmm this book earlier said that it always assumed that (a,n)=1 and (b,n)=1 without stating it. then (ab,n)=1 so (ab)x=1 mod n must have solution, sorry, i not state this earlier.

 

[jbunniii]

Do you know any group theory? Let A = \langle a\rangle and B = \langle b\rangle be the cyclic groups generated by a and b, respectively.

Then |A| = o(a) = h and |B| = o(b) = k are relatively prime. This implies a key fact: A \cap B = 1, the trivial group.

Now consider (ab)^r. For what values of r can (ab)^r = 1? This is the same as a^r b^r = 1, or equivalently a^r = b^{-r}. So we have a common element, x = a^r = b^{-r}, which must be in both A and B, right? What does this imply?

 

[annoymage]

yea, but i just going through cyclic group very fast once since i'll be learning that next semester.

but that means <br /> a^r = b^{-r}=1<br />right? and easily can show hk l r, problem solved, thanks jbunnii ^^