Two more simple cyclic group problems

  • Thread starter radou
  • Start date
  • #1
radou
Homework Helper
3,115
6

Homework Statement



1) let <a> be a cyclic group of order n. If n and m are relatively prime, then the function f(x) = x^m is an automorphism of <a>.

2) Let G be a group and a, b be in G. Let a be in <b>. Then <a> = <b> iff a and b have the same order.

The Attempt at a Solution



1) It is trivial to check that for any x, y in <a>, f(xy) = f(x)f(y). For injectivity, let x^m = y^m. We have x = a^k and y = a^j, for some integers k and j. Now a^(km) = a^(jm) implies that km = jm, which implies k = j, and hence x = y. (Since, all the powers of a are distinct, so if km and jm were distinct, then a^(km) = a^(jm) couldn't possibly hold).

I have a bit of a problem with surjectivity. When I look at examples of cyclic groups, the whole problem is very obvious intuitively - for any element, we can find adjust another one which will give the first one after multiplying m times - but, formally... Let y be in <a>, so y = a^k, for some integer k. We need to show that there exists some element a^j in <a> such that a^(jm) = a^k. I guess here the fact that m and n are relatively prime comes in... But I can't find the solution.

2) Since a is in <b>, a = b^k, for some k. Let <a> = <b>. Then, by definiton, the orders of these groups are equal, and by definition again, the orders of a and b must be equal. For the converse, let ord(a) = ord(b) = p. Is x is in <a> it is clearly in <b>, since a = b^k. Let x be in <b>. so x = b^j, for some j. Now, since the orders of b and a = b^k are equal, this means that there are p distinct powers of b and of b^k. But a power of b^k is a power of b, too, and hence <a> must equal <b>.
 

Answers and Replies

  • #2
22,089
3,297
1) It is trivial to check that for any x, y in <a>, f(xy) = f(x)f(y). For injectivity, let x^m = y^m. We have x = a^k and y = a^j, for some integers k and j. Now a^(km) = a^(jm) implies that km = jm, which implies k = j, and hence x = y. (Since, all the powers of a are distinct, so if km and jm were distinct, then a^(km) = a^(jm) couldn't possibly hold).

Can you explain why a^(km)=a^(jm) implies that km=jm. If I remember well, this does not hold in general... You will have to use theorem 10.5 on this...

I have a bit of a problem with surjectivity. When I look at examples of cyclic groups, the whole problem is very obvious intuitively - for any element, we can find adjust another one which will give the first one after multiplying m times - but, formally... Let y be in <a>, so y = a^k, for some integer k. We need to show that there exists some element a^j in <a> such that a^(jm) = a^k. I guess here the fact that m and n are relatively prime comes in... But I can't find the solution.

So we must find j such that jm=k (mod n). Now use the fact that m has an inverse in [tex]\mathbb{Z}_n[/tex] to find an explicit form of j.

2) Since a is in <b>, a = b^k, for some k. Let <a> = <b>. Then, by definiton, the orders of these groups are equal, and by definition again, the orders of a and b must be equal. For the converse, let ord(a) = ord(b) = p. Is x is in <a> it is clearly in <b>, since a = b^k. Let x be in <b>. so x = b^j, for some j. Now, since the orders of b and a = b^k are equal, this means that there are p distinct powers of b and of b^k. But a power of b^k is a power of b, too, and hence <a> must equal <b>.

Looks OK.
 
  • #3
radou
Homework Helper
3,115
6
Can you explain why a^(km)=a^(jm) implies that km=jm. If I remember well, this does not hold in general... You will have to use theorem 10.5 on this...

Hmm, I followed this logic.

a^(km) and a^(jm) are powers of a. They are equal. If km would be different from jm, then a^(km) and a^(jm) would necessarily be different, not? It seemed I could conclude that km = jm from this...
 
  • #4
22,089
3,297
No, this is not correct. For example, if you are working in a cyclic group of order 6 and generator a, then

[tex]a=a^7=a^{13}=...[/tex]

So it doesn't necessarily follow that the exponents are equal. What you do have is the following in a group of order n:

[tex]a^k=a^p~\Rightarrow~a^{k-p}=1~\Rightarrow~n~\text{divides}~k-p[/tex].
 
  • #5
radou
Homework Helper
3,115
6
Yes, that was a stupid line of reasoning from my side...It would hold it we'd be talking about an infinite cyclic group, though, right?

OK, I'll think about this...
 
  • #6
22,089
3,297
Yes, that was a stupid line of reasoning from my side...It would hold it we'd be talking about an infinite cyclic group, though, right?

OK, I'll think about this...

Yes, in an infinite group, you are correct!
 
  • #7
radou
Homework Helper
3,115
6
OK, it follows that if a^(km) = a^(jm), we have a^(km - jm) = e, and by theorem 10.5. m(k - j) = nq, for some integer q, where n is the order of a. The hint says to use Ex. B3., i.e. if b is in <a>, then ord(a) = ord(b)p (i.e. the order of b is a factor of the order of a. Hence, we can conclude that n = kmp1 =jmp2, for some integers p1 and p2.

Now I have to use the fact that n and m are relatively prime, and here my knowledge gaps in number theory become obvious.

From the equations above I can deduce that kp1 = jp2, but that doesn't really help.
 
  • #8
22,089
3,297
I'm a bit confused. Can you explain how you used exercise B3. What did you take for b?
 
  • #9
radou
Homework Helper
3,115
6
For b I took the elements a^(km) and a ^(jm), although the effect is the same as if I took a^k and a^j.
 
  • #10
22,089
3,297
For b I took the elements a^(km) and a ^(jm), although the effect is the same as if I took a^k and a^j.

Yes, but then I'm confused on what comes next. The order of a^(km) is not km. It's more like n/gcd(km,n) if I'm correct.
Also, it doesn't generally hold that n=kmp1. It does hold that there exist something such that qn=kmp1. So a multiple of n equals kmp1... (in other words kmp1=0 (mod n)).

This exercise actually becomes easier if you use Bezout's theorem. It states that if n and m are coprime, then there exist l and k such that nl+km=1. Perhaps you should attempt to show this...
 
  • #11
radou
Homework Helper
3,115
6
Ahhh, of course, I know that the order of a^(km) is not km, I was being harsh again! OK, I'll stop writing nonsense and get back when I have something better...
 
  • #12
22,089
3,297
If you want to you Bezout's theorem, then here's an outline to prove it:

1) Consider the group [tex]n\mathbb{Z}+m\mathbb{Z}[/tex]. Prove that it is a subgroup from [tex]\mathbb{Z}[/tex]
2) Conclude from 1 that [tex]n\mathbb{Z}+m\mathbb{Z}[/tex] is cyclic, and thus from the form [tex]d\mathbb{Z}[/tex].
3) Use coprimality of n and m to show that d=1.

The general statement of Bezout's theorem is valid even if n and m are not coprime. It states [tex]n\mathbb{Z}+m\mathbb{Z}=gcd(n,m)\mathbb{Z}[/tex]. But you won't need that...
 
  • #13
radou
Homework Helper
3,115
6
Thanks for the hint, but I think I'll try to prove it witout this theorem...Btw, I'm not sure what nZ + mZ stands for, perhaps a sum of quotient groups, but I didn't reach that part yet, it may be too much for now.
 
  • #14
22,089
3,297
Well, you can try to prove it without Bezout's theorem, but the problem is that what you're trying to show is equivalent to Bezout's theorem. So you'll end up proving it anyways :biggrin: But I'm not going to stop you :tongue2:

btw, [tex]n\mathbb{Z}+m\mathbb{Z}=\{nz+mz^\prime~\vert~z,z^\prime\in \mathbb{Z}\}[/tex]. It's the set of all "linear" combinations of n and m, if you want to use linear algebra terminology...
 
  • #15
radou
Homework Helper
3,115
6
Well, if that's the case, then it's different. OK. :cool:
 
  • #16
radou
Homework Helper
3,115
6
OK, parts 1 and 2 are trivial - for any two elements in nZ + mZ, their sum is in nZ + mZ too, and every element of nZ + mZ has in inverse in nZ + mZ, it's really obvious, and, since Z is cyclic, and nZ + mZ is proven to be a subgroup of Z, nZ + mZ must itself be cyclic. Hence, it has a generator d. I'll have to think a bit for the third part (no hints please).
 
  • #17
radou
Homework Helper
3,115
6
But just a sec, isnt dZ simply Z if d = 1? Or I misunderstood the notation... i.e. in the case where n and m are coprime, this subgroup equals Z? Is that what we need to prove?
 
  • #18
22,089
3,297
OK, parts 1 and 2 are trivial - for any two elements in nZ + mZ, their sum is in nZ + mZ too, and every element of nZ + mZ has in inverse in nZ + mZ, it's really obvious, and, since Z is cyclic, and nZ + mZ is proven to be a subgroup of Z, nZ + mZ must itself be cyclic. Hence, it has a generator d. I'll have to think a bit for the third part (no hints please).

That's already correct!
 
  • #19
22,089
3,297
But just a sec, isnt dZ simply Z if d = 1? Or I misunderstood the notation... i.e. in the case where n and m are coprime, this subgroup equals Z? Is that what we need to prove?

Yes, that is exactly what you need to show, that nZ+mZ=Z!
 
  • #20
radou
Homework Helper
3,115
6
I'm trying to motivate myself to find a pattern, I wrote down the set nZ + mZ for n = 3 and m = 8... It's obvious that for any integer x, one can find k, l such that x = mk + nl. Now I only need to formalize this.

Edit: no hints! :biggrin:

Edit 2: if I prove this, the theorem follows easily...
 
  • #21
22,089
3,297
Say if you want a hint :biggrin: And don't look too far...
 
  • #22
radou
Homework Helper
3,115
6
Ahhh, a small hint, please! :tongue2: :rolleyes:
 
  • #23
22,089
3,297
Is a in dZ? And what does this imply?
 
  • #24
radou
Homework Helper
3,115
6
Is a in dZ? And what does this imply?

a in dZ? Isn't <a> an arbitrary cyclic group? dZ is an additive group, right? i.e. dZ = {dz : z is in Z}, for some fixed integer d.

If a is in dZ then a = dz, for some integer z.
 
  • #25
22,089
3,297
Oh, I'm sorry. I meant: are n and m in dZ? I mixed up with the a...
 

Related Threads on Two more simple cyclic group problems

  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
4
Views
5K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
1
Views
953
Replies
4
Views
550
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
8K
  • Last Post
Replies
2
Views
3K
Top