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}=1$mod 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 $a^r = b^{-r}=1$right? and easily can show hk l r, problem solved, thanks jbunnii ^^