Order of element

  • Thread starter annoymage
  • Start date
  • #1
362
0

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,[itex] a^k=1 mod n[/itex]

The Attempt at a Solution



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

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

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

it can be shown that [itex](ab)^q=1 mod n[/itex], 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?
 
Last edited:

Answers and Replies

  • #2
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,473
255
it can be shown that [itex](ab)^q=1 mod n[/itex], 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 [itex]o(ab) | hk[/itex]. It suffices to show that

[tex](ab)^{hk} = 1[/tex]

But

[tex](ab)^{hk} = a^{hk} b^{hk} = (a^h)^k (b^k)^h = (1)(1) = 1[/tex]

However, this isn't enough to imply that [itex]o(ab) = hk[/itex]. For that, you will need to use the fact that [itex]gcd(h,k) = 1[/itex].
 
  • #3
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,473
255
P.S. You didn't specify what group or ring or field you are working in. I infer that [itex]a[/itex] and [itex]b[/itex] are elements of [itex]\mathbb{Z}/(n)[/itex] (integers modulo n). However, you did not mention whether [itex]n[/itex] is prime. If not, then be aware that not every element necessarily has an order. For example, in [itex]\mathbb{Z}/(4)[/itex], consider the element [itex]a = 2[/itex]. There is no [itex]k[/itex] for which [itex]2^k = 1 (\mod 4)[/itex], so [itex]w[/itex] doesn't have an order in [itex]\mathbb{Z}/(4)[/itex].

So if [itex]n[/itex] is not necessarily prime, you need to do a bit more work to justify whether [itex]o(ab)[/itex] is even defined.
 
  • #4
362
0
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 [itex]o(a^k)=h[/itex] and [itex]o(b^h)=k[/itex] since (h,k)=1

this one im not sure, r l hk then let e be such that re=hk
so then [itex](a^k)^r=(a^k)^{hk/e}=1^{k/e}=1[/itex]mod n, so is it ok? because im 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.
 
Last edited:
  • #5
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,473
255
Do you know any group theory? Let [itex]A = \langle a\rangle[/itex] and [itex]B = \langle b\rangle[/itex] be the cyclic groups generated by [itex]a[/itex] and [itex]b[/itex], respectively.

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

Now consider [itex](ab)^r[/itex]. For what values of [itex]r[/itex] can [itex](ab)^r = 1[/itex]? This is the same as [itex]a^r b^r = 1[/itex], or equivalently [itex]a^r = b^{-r}[/itex]. So we have a common element, [itex]x = a^r = b^{-r}[/itex], which must be in both [itex]A[/itex] and [itex]B[/itex], right? What does this imply?
 
Last edited:
  • #6
362
0
yea, but i just going through cyclic group very fast once since i'll be learning that next semester.

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

Related Threads on Order of element

  • Last Post
Replies
1
Views
916
Replies
1
Views
405
  • Last Post
Replies
4
Views
4K
Replies
3
Views
3K
  • Last Post
2
Replies
34
Views
1K
  • Last Post
Replies
3
Views
2K
Replies
11
Views
14K
  • Last Post
Replies
1
Views
1K
Replies
11
Views
490
Top