Thread: Finding a Generator of a Cyclic Group

There's something I'm a bit confused about.

There's a theorem that states that if the order of a group is n, then every k > 1 that satisifes gcd(k,n) = 1 will be a generator of the group.

So if we take U(9) = {1,2,4,5,7,8}, and the order n = 6 and the generators in this case are supposed to be 5 and 7, since gcd(5,6) = gcd(7,6) = 1.

<5> = {5,7,8,4,2,1} is okay, but
<7> = {7,4,1}
and instead <2> = {2,4,8,7,5,1}, even though gcd(2,6) = 2.

What's the problem here?

Originally Posted by Koaske

There's something I'm a bit confused about.

There's a theorem that states that if the order of a group is n, then every k > 1 that satisifes gcd(k,n) = 1 will be a generator of the group.


No, what that theorem says is that if g is a generator of that cyclic group of order n, then any other

generator is of the form , and the other direction is true, too.

Tonio

So if we take U(9) = {1,2,4,5,7,8}, and the order n = 6 and the generators in this case are supposed to be 5 and 7, since gcd(5,6) = gcd(7,6) = 1.

<5> = {5,7,8,4,2,1} is okay, but
<7> = {7,4,1}
and instead <2> = {2,4,8,7,5,1}, even though gcd(2,6) = 2.

What's the problem here?

.

Ah, I see. So here it's <2^k> , and k = 1 makes it <2>, and k = 5 makes it <5>.

This leads me to another problem though... To prove that a very big group is cyclic, U(101) = {1,2,...,99,100}, to be exact, I would first have to find this element g to find all other generators. If this was a smaller group, I would just go through the elements one by one, but here it would require too much work. I suppose there has to be an easier solution, but I don't know what it is...

Finding a specific generator in such a large group can be tough.

But IS cyclic, as 101 is prime. In fact, it is true that if is an odd prime, then is cyclic, for any .

What if we knew that <a> = G for some a? Would there be any easier way to prove that a really generates the whole group, other than going through all a^k ?

Originally Posted by Koaske

What if we knew that <a> = G for some a? Would there be any easier way to prove that a really generates the whole group, other than going through all a^k ?

This question doesn't make any sense.

"If we knew that a generates G, could we prove that a generates G?"

Maybe you mean something else?

What I meant is that if we ASSUME that some element a generates the group. We would still have to prove that assumption though. For example, let's say that we have a hunch that 5 would generate U(9), but we don't want to go through all 5^k to prove it. Would there be another way?

Well...

You could do it a little more simply than that, but it would still require some computation.

The order of the group is . Thus any element of this group has order 1, 2, 3, or 6.

If you could show that an element doesn't have order 1, 2, or 3, then it would necessarily have order 6, from which it would follow that it generates the group.

So in case of U(101), which has 100 = 2² * 5² elements, I would have to find an element that has order of at least 51?

I guess. But you just need an element whose order is none of the proper divisors of 100.

So you don't need to check every power. Given an element, raise it to the powers 1, 2, 4, 5, 10, 20, 25, 50 (yea, there's work to do there). If none of these give 1, the element must generate the group.

Originally Posted by Koaske

So in case of U(101), which has 100 = 2² * 5² elements, I would have to find an element that has order of at least 51?

As , an element is a generator iff

, and something similar is

true for any prime 1 mod 4 (can you give the general claim and its proof?)

If then it is easier: is a generator iff .

The general problem of finding a primitive root modulo p (which is what's called a generator

of U(p)) has no general acceptable easy algorithm to do it.

Tonio