Register to reply 
Does Z*(n) always have a generator?by dumbQuestion
Tags: generator 
Share this thread: 
#1
Feb813, 05:16 PM

P: 126

Hey this question is going to sound really basic and dumb but I'm new to abstract algebra and not very good at this stuff. When I am talking about Z*(n), to be clear, I mean the multiplicative group of integers mod n, or the way I'm always thinking about it, the units of Z(n). (I'm not sure what the actual name for Z(n) is, but it's the equivalence classes of the integers mod n, so for example, Z(3) = {[0],[1],[2]}, Z(4) = {[0],[1],[2],[3]}, etc.)
Now, it seems like Z*(n) always has some generator. But I don't want to just assume that's the case. I understand that Z*(n) is cyclic, but does every cyclic group have a generator? (or is this just part of the definition of being cyclic  that it's a group built up by some generator) Is there a theorem that says Z*(n) is cyclic? Also, how can I tell how many generators of Z*(n) there are? For example when I'm building up Dirichlet tables for Z*(n) I notice for example Z*(5) has two generators: [2] and [3], while some of the others only have a single generator. Is there any theorem that tells me exactly how many generators there are? 


#2
Feb813, 05:41 PM

Mentor
P: 18,333

However, when n is a prime number, then it is true. In general, if you have a field, then every finite, multiplicative subgroup of the field is cyclic. Some proofs can be found here: http://mathoverflow.net/questions/54...ldsarecyclic In the case of [itex]\mathbb{Z}^*(n)[/itex]. If n is a prime, then this is cyclic with order n1. So the number of generators is given by [itex]\varphi(n1)1[/itex]. http://en.wikipedia.org/wiki/Euler%27s_totient_function 


#3
Feb913, 05:08 PM

P: 126

THank you so much. I did not realize that Z^{*}(n) was not cyclic and feel kind of stupid now for thinking it (always) was.
And wow... thank you more than you know for letting me know about that relationship between the Euler totient function and the number of generators of a cyclic group. This is extremely helpful! 


#4
Feb913, 08:57 PM

P: 126

Does Z*(n) always have a generator?
Wait... I'm confused about one thing. How can the order of every element a in a cyclic group be, t/gcd(k,t) where k is the order of the group and a = g^t for a generator g. The reason I ask is because gcd(k,1) = 1, and so that makes it sound like the order of 1 will be t, which would make it a generator, but it's never a generator. I imagine thats why you're subtracting the 1, but I was just wondering if you could clarify which theorem you were pointing to to get that because again I'm confused why it makes it look like the identity is a generator.



#5
Feb913, 09:02 PM

Mentor
P: 18,333

This actually implies that the right definition of gcd(k,0) would be gcd(k,0)=k. 


#6
Feb913, 09:11 PM

P: 126

oooh ok that makes sense. Let me make sure I understand though. So say we are in Z*(n) and say we have a generator, say [2]. [2] being a generator means that [2][2]= some other element in Z*(n), and [2][2][2] yet another... all the way until we multiply n of them to get [2][2]...[2] (n times) = [1]. So [2]^n = 1, but [n]=[0], so is that why you are referring to using 0 instead?



Register to reply 
Related Discussions  
Mapping generator to generator in cyclic groups.  Calculus & Beyond Homework  2  
Van De Graff Generator: Explanations to why object repel generator  Introductory Physics Homework  1  
Generator Shaft Power (Input) to Generator Out  Mechanical Engineering  1  
Van de Graff Generator: Electrostatics, why do objects repel the generator  Advanced Physics Homework  0  
Flywheel Generator  Split from Propane Solar Collector/Generator Thread  Mechanical Engineering  52 