# Finding a Generator of a Cyclic Group

• Mar 9th 2011, 01:25 PM
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?
• Mar 9th 2011, 01:32 PM
tonio
Quote:

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 $\displaystyle g^k\,,\,\,(k,n)=1$ , 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?

.
• Mar 9th 2011, 02:21 PM
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...
• Mar 9th 2011, 05:10 PM
topspin1617
Finding a specific generator in such a large group can be tough.

But $\displaystyle U(\mathbb{Z}_{101})$ IS cyclic, as 101 is prime. In fact, it is true that if $\displaystyle p$ is an odd prime, then $\displaystyle U(\mathbb{Z}_{p^n})$ is cyclic, for any $\displaystyle n\geq 1$.
• Mar 9th 2011, 05:16 PM
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 ?
• Mar 9th 2011, 05:17 PM
topspin1617
Quote:

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?
• Mar 9th 2011, 05:26 PM
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?
• Mar 9th 2011, 05:30 PM
topspin1617
Well...

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

The order of the group $\displaystyle U(\mathbb{Z}_9)$ is $\displaystyle \varphi (9)=3\cdot 2=6$. 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.
• Mar 9th 2011, 05:37 PM
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?
• Mar 9th 2011, 05:44 PM
topspin1617
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.
• Mar 9th 2011, 06:40 PM
tonio
Quote:

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 $\displaystyle 101=1\!\!\pmod 4\,\,and\,\,\phi(101)=100$ , an element $\displaystyle g\in U(101)$ is a generator iff

$\displaystyle g^{50}=-1\!\!\pmod{101}\,\,and\,\,g^{25}\neq 1\!\!\pmod{101}$ , and something similar is

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

If $\displaystyle p=3\!\!\pmod 4$ then it is easier: $\displaystyle g\in U(p)$ is a generator iff $\displaystyle g^{\frac{p-1}{2}}=-1\!\!\pmod p$.

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