Cyclic group generator problem

[radou]

Homework Statement

Let <a> be a cyclic group, where ord(a) = n. Then a^r generates <a> iff r and n are relatively prime.

The Attempt at a Solution

OK, let n and r be relatively prime. Then ord(a^r) = n. We need to show that for some j, there exists an integer k such that (a^r)^k = a^j. Now, every power of a equals one of the powers in <a>. Hence, for any k, a^(rk) equals some a^p. By inspecting the proof of that fact, I concluded that the power rk+1, equals a^(p+1), if we keep all the factors obtained by the division algorithm the same, and only increase the remainder by 1 (I don't see why we couldn't do this). This way, we can generate every element of <a>, and hence a^r generates <a>.

Now, for the other direction, if a^r generates <a>, and if we show that ord(a^r) = n, then we are done, since r and n must be relatively prime then (I proved this fact in another exercise). We see that (a^r)^n = (a^n)^r = e. Now, assume there is some j < n such that (a^r)^j = e. But the, since a^r is a generator of <a>, <a> would have less than n elements, contrary to the starting assumption, hence the order of a^r equals n.

 

[micromass]

All seems well! I just have a few comments:

OK, let n and r be relatively prime. Then ord(a^r) = n.

How do you know this? Have you proven this in an earlier exercise?

We need to show that for some j, there exists an integer k such that (a^r)^k = a^j. Now, every power of a equals one of the powers in <a>. Hence, for any k, a^(rk) equals some a^p. By inspecting the proof of that fact, I concluded that the power rk+1, equals a^(p+1), if we keep all the factors obtained by the division algorithm the same, and only increase the remainder by 1 (I don't see why we couldn't do this). This way, we can generate every element of <a>, and hence a^r generates <a>.

The proof seems good, but I think you're probably making it a bit hard on yourself. This is what I did: if ord(a^r)=n, then <a^r> has n elements. But &lt;a^r&gt;\subseteq &lt;a&gt; and <a> also has n elements. This implies immediately that <a^r>=<a>.

Now, for the other direction, if a^r generates <a>, and if we show that ord(a^r) = n, then we are done, since r and n must be relatively prime then (I proved this fact in another exercise). We see that (a^r)^n = (a^n)^r = e. Now, assume there is some j < n such that (a^r)^j = e. But the, since a^r is a generator of <a>, <a> would have less than n elements, contrary to the starting assumption, hence the order of a^r equals n.

This seems good!

 

[radou]

How do you know this? Have you proven this in an earlier exercise?

Yes I have, I forgot to mention that!

The proof seems good, but I think you're probably making it a bit hard on yourself. This is what I did: if ord(a^r)=n, then <a^r> has n elements. But &lt;a^r&gt;\subseteq &lt;a&gt; and <a> also has n elements. This implies immediately that <a^r>=<a>.

Actually, this is so obvious, you're right! It's a better way to prove it. Since (a^r)^k is a power of a, it must be one of the powers a^0, ... , a^(n-1). And this holds for any k. And because of the order, these powers must be distinct. Hence, our result is proven!

Btw, it just occurred to me that my "proof" wasn't quite valid. rk + 1 is not a factor of rk, right? And I'm only interested in powers of the form r(k+z) actually, where z is any integer.

 

[micromass]

Btw, it just occurred to me that my "proof" wasn't quite valid. rk + 1 is not a factor of rk, right? And I'm only interested in powers of the form r(k+z) actually, where z is any integer.

To be honest, the proof wasn't very clear to me. So I interpreted it a bit and I thought you meant the right thing. But rk+1 is never a factor of rk, so it probably doesn't work...

I actually find working with cyclic groups to be quite annoying But luckily there's much more to algebra than cyclic things...

 

[radou]

But luckily there's much more to algebra than cyclic things...

Well, I was definitely hoping for that!

Thanks!