Two more simple cyclic group problems

[radou]

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>.

 

[micromass]

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 \mathbb{Z}_n 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.

 

[radou]

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...

 

[micromass]

No, this is not correct. For example, if you are working in a cyclic group of order 6 and generator a, then

a=a^7=a^{13}=...

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

a^k=a^p~\Rightarrow~a^{k-p}=1~\Rightarrow~n~\text{divides}~k-p.

 

[radou]

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...

 

[micromass]

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!

 

[radou]

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.

 

[micromass]

I'm a bit confused. Can you explain how you used exercise B3. What did you take for b?

 

[radou]

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.

 

[micromass]

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...

 

[radou]

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...

 

[micromass]

If you want to you Bezout's theorem, then here's an outline to prove it:

1) Consider the group n\mathbb{Z}+m\mathbb{Z}. Prove that it is a subgroup from \mathbb{Z}
2) Conclude from 1 that n\mathbb{Z}+m\mathbb{Z} is cyclic, and thus from the form d\mathbb{Z}.
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 n\mathbb{Z}+m\mathbb{Z}=gcd(n,m)\mathbb{Z}. But you won't need that...

 

[radou]

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.

 

[micromass]

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 But I'm not going to stop you

btw, n\mathbb{Z}+m\mathbb{Z}=\{nz+mz^\prime~\vert~z,z^\prime\in \mathbb{Z}\}. It's the set of all "linear" combinations of n and m, if you want to use linear algebra terminology...

 

[radou]

Well, if that's the case, then it's different. OK.

 

[radou]

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).

 

[radou]

But just a sec, isn't 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?

 

[micromass]

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!

 

[micromass]

But just a sec, isn't 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!

 

[radou]

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!

Edit 2: if I prove this, the theorem follows easily...

 

[micromass]

Say if you want a hint And don't look too far...

 

[radou]

Ahhh, a small hint, please!

 

[micromass]

Is a in dZ? And what does this imply?

 

[radou]

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.

 

[micromass]

Oh, I'm sorry. I meant: are n and m in dZ? I mixed up with the a...

 

[radou]

Well, certainly they are. And we concluded that nZ + mZ must be a cyclic group with some generator d. Hence n = dp and m = dq, for some integers p and q.

 

[micromass]

So d divides both n and m...

 

[radou]

So d divides both n and m...

Ah, of course! Since m and n are relatively prime, it follows that d = 1!

So, we proved the theorem. I.e.:

Let m and n be relatively prime. Then, for any given integer x, there exist integers k, l such that mk + nl = x.

Specially, for x = 1 this must hold.

OK, now I'll see how that helps me to solve the problem...

 

[radou]

OK, we want to prove injectivity of the map f : <a> --> <a> given with f(x) = x^m, where m is relatively prime to ord(a) = n.

Let x^m = y^m, i.e. a^(km) = a^(jm), for some integers k, j. It follows that a^(km - jm) = e. From Theorem 10.5. I conclude that km - jm = np, for some integer p. Somehow, using the theorem just proven, I need to show that k = j, i.e. x = y, right?

 

[micromass]

OK, we want to prove injectivity of the map f : <a> --> <a> given with f(x) = x^m, where m is relatively prime to ord(a) = n.

Let x^m = y^m, i.e. a^(km) = a^(jm), for some integers k, j. It follows that a^(km - jm) = e. From Theorem 10.5. I conclude that km - jm = np, for some integer p. Somehow, using the theorem just proven, I need to show that k = j, i.e. x = y, right?

Well, you don't need to show that k=j, that won't be true in general. You need to show that k-j=qn for some q. The reason is that a^k might equal a^j, even if k and j are not equal. (Of course, if you assume k and j to be less then n, then a^k=a^j is equivalent with j=k...)

Here's a small hint (don't read if you don't want a hint)

The easiest way to show this is by calculating modulo n.
You need to show that k-j=qn. This means that you need to show that k=j (mod n).
You have that km-jm=np, this means that km=jm (mod n). So the only thing you need to do is find an inverse of m in modulo n.

 

[radou]

Hm, km = jm (mod n) means that n divides km - jm = m(k - j). Now, I'm not sure about this, I tried it out on some numeric examples and it seems to work, and since you're here to ask, does it follow that n divides k - j, since m and n are relatively prime (i.e. m cannot divide n)?

P.S. If this was a stupid question, forgive me, I'm still warming up on this topic.

 

[micromass]

Yes, you are correct: if n divides m(k-j), then it must imply that n divides k-j (if n and m are coprime). But you have to prove it rigourously...

 

[radou]

Yes, I know, I'll try to prove it. Once I do so, the rest is trivial, since then a^k = a^(qn+j) = a^(qn)a^j = a^j.

 

[micromass]

What does Bezout's theorem give you in modulo n?

 

[radou]

Hm, no hints yet, but can this be proven so that I assume the contrary, i.e. that n doesn't divide k - j either? I'm messing with some inequalities and trying to apply Bezout's theorem, but I'm still getting nowhere. If the proof involvec modulo n congruence classes, I'm still not into that yet, so there may be something I don't see right away...

 

[micromass]

I'm not sure, I would go for a direct proof. I think that is easiest...
But I suppose contradiction may work, but I don' know how at this point...

The proof is easiest if you work with modulo congruence classes. But I understand that you don't really want to use it because you don't feel comfortable with it. But after you figured out the proof for this, I really suggest transforming the proof so that it works with modulo n to. Modulo n congruences is really a very important tool algebra!

 

[radou]

I'm not sure, I would go for a direct proof. I think that is easiest...
But I suppose contradiction may work, but I don' know how at this point...

The proof is easiest if you work with modulo congruence classes. But I understand that you don't really want to use it because you don't feel comfortable with it. But after you figured out the proof for this, I really suggest transforming the proof so that it works with modulo n to. Modulo n congruences is really a very important tool algebra!

Hmm, OK, I'll skip to Chapter 23 then for a while, I hope it will help to solve this problem finally...

 

[radou]

Btw, I don't understand why the author put this exercise in a section too early... i.e. if there is no other "decent" way to prove this without using congruence modulo classes... Specially considering the fact that most of the exercises are far more easy than this one.

 

[micromass]

Well, you don't need to use module classes. The proof is not that difficult if you don't use them. However, with module classes, the proof is more natural. That's why I prefer it that way.

It's of course another possibility that there's a really elegant proof for this, but I really don't see it. What we've done so far is the way I've seen it, and how it is in all the books I've seen. However, the fact that this exercise comes so early, might indicate that there is a short proof of this...

So in short, you don't need chapter 22 for this, but I certainly suggest coming back to the problem once you did chapter 22. Since the proof will become more natural and easier then what it is now...

 

[radou]

Hmm, yes...

I started with m(k - j) = pn. I tried to assume n doesn't divide k - j, so we have k - j\neq zn, for every integer z. I tried to multiply with m and apply Bezout's theorem in order to obtain a contradiction somehow, but I think this won't work. Any thoughts perhaps?

I hate to say that, but it's probably the best to leave that exercise for later.

 

[micromass]

Alright, I'll give a hint. It should be easy once you did this:

Bezout's theorem gives us an x and y such that mx+yn=1.

Now, assume that m(k-j)=pn. Now multiply both sides by x. This should solve the problem. Note that it isn't clear why multiplying by x gives a nice answer, but this will become clear once you studied modulo congruences...

 

[radou]

Alright, I'll give a hint. It should be easy once you did this:

Bezout's theorem gives us an x and y such that mx+yn=1.

Now, assume that m(k-j)=pn. Now multiply both sides by x. This should solve the problem. Note that it isn't clear why multiplying by x gives a nice answer, but this will become clear once you studied modulo congruences...

Hm, I can't see how this gives the solution... And how do we know that x is non-zero?

 

[micromass]

Well, if x is zero, then yn=1, thus n=1. Then we are working in the cyclic group with 1 element (i.e. the trivial group).

If x is nonzero, then we multiply both sides of m(k-j)=pn by x. We get xm(k-j)=pn. But since xm+yn=1, this gives us (1-yn)(k-j)=pn. Working out the brackets gives us k-j=n(p+yk-jy).
Thus we have found a natural number q such that k-j=qn. This yields that a^k=a^j.

 

[radou]

Well, if x is zero, then yn=1, thus n=1. Then we are working in the cyclic group with 1 element (i.e. the trivial group).

If x is nonzero, then we multiply both sides of m(k-j)=pn by x. We get xm(k-j)=pn. But since xm+yn=1, this gives us (1-yn)(k-j)=pn. Working out the brackets gives us k-j=n(p+yk-jy).
Thus we have found a natural number q such that k-j=qn. This yields that a^k=a^j.

Hm, after multiplying both sides of m(k - j) = pn by x, don't we get xm(k - j) = xpn? But that doesn't matter, since (1 - yn)(k - j) = xpn ==> k - j = yn(k - j) + xpn = (y(k - j) + xp)n, which demonstrates that our mapping is injective.

 

[micromass]

Hm, after multiplying both sides of m(k - j) = pn by x, don't we get xm(k - j) = xpn?

Yes, I'm sorry. Of course I should have multiplied both sides... But it doesn't matter that much...

 

[radou]

OK, no problem! Then there's only surjectivity left to show, i.e. let b = a^k be an element of <a>, we need to show that there exists some integer j such that (a^j)^m = a^k. Now, I used an exercise from the next exercise section to prove this (which probably implies there's another way to prove it): since m and n are relatively prime, a^m is a generator of <a>. Then clearly there exists an integer j such that (a^m)^j = (a^j)^m = a^k.

 

[micromass]

Yes, this is correct. But note that there are some more ways of proving this.

The easiest way is by noting the following: if X and Y are finite sets such that |X|=|Y| (i.e. X and Y have the same number of elements) and if f f:X--> Y is a function, then f is injective iff it is surjective.

This immediately implies surjectivity, since you have already proven injectivity.
It's really a handy property: if you have two finite groups G and H and you want to prove that they are isomorphic, then you just need to check that G and H have the same elements and that there exists an injective homomorphism between them. This is fun because you never need to show surjectivity...

Another way is through Bezout's theorem. Take a^k. You need to find a j such that a^(jm)=a^k. Thus you need to find a j such that jm-k=pn for some p. By Bezout's theorem, you can find xm+yn=1. Take j=xk. Then jm-k=xmk-k=k-ynk-k=ykn. Thus p=yk in this case...

But I think your proof is the cleanest possible proof for this...

 

[radou]

Yes, this is correct. But note that there are some more ways of proving this.

The easiest way is by noting the following: if X and Y are finite sets such that |X|=|Y| (i.e. X and Y have the same number of elements) and if f f:X--> Y is a function, then f is injective iff it is surjective.

Ahh, of course, I should have thought of this, since this was even an exercise in an earlier section!

Thanks!