Register to reply 
Efficient way to find which element of Z*n has largest order? 
Share this thread: 
#1
Feb1313, 07:26 AM

P: 126

Hey, I had two separate questions. (When I say Z*(n) I'm denoting the multiplicative group of integers mod n, namely, the units of Z(n))
First off, I know that if n is prime, that Z*(n) is cyclic. But this is not a biconditional statement. Is there any theorem which tells me conditions under which Z*(n) is not cyclic? I can't just say n is not prime so Z*(n) is not cyclic. Right? Second question  if I know that Z*(n) is cyclic, then I know it has a generator. But other than going through each and every element and multiplying them out, is there an efficient way to find out which elements are generators? Also, in the case that Z*(n) isn't cyclic (like say Z*(12)) is there a way to find which element has the highest order? If anyone can point me to the proper theorems, I would be extremely grateful! 


#2
Feb1313, 12:16 PM

Engineering
Sci Advisor
HW Helper
Thanks
P: 6,953

Start by thinking about the case where n = pq where p and q are both prime. (For example, n = 6)
When you see what is going on, generailze it to the case where n has more than two prime factors. 


#3
Feb1313, 03:36 PM

Sci Advisor
HW Helper
P: 9,453

Aleph Zero makes a good suggestion. It is not so trivial in general however, when there are repeated factors. There is a discussion starting on p. 48. of these notes, of when the group is cyclic:
http://www.math.uga.edu/%7Eroy/8442.pdf In fact your question as to precisely how to identify generators is perhaps even less trivial. There may even be some open questions surrounding that matter, as I recall. 


#4
Feb1313, 06:57 PM

P: 126

Efficient way to find which element of Z*n has largest order?
Thank you guys for the links and the responses!
I also found this: "Zn*, the multiplicative group modulo n, is cyclic if and only if n is 1 or 2 or 4 or p^{k} or 2p^{k} for an odd prime number p and k ≥ 1." But I did not see a proof provided for it. I think this might tie in with what you were saying AlephZero 


#5
Feb1313, 10:25 PM

Sci Advisor
HW Helper
P: 9,453

if you look at the links i provided you will find complete proofs of these facts.



#6
Feb1313, 11:27 PM

P: 126

Yeah I have spent the last couple hours looking at the doc you provided and some other documents I've hunted down. Very helpful! I need to purchase a good number theory text book to have on hand it seems! Thank you again!



Register to reply 
Related Discussions  
An efficient way to find perfect squares?  Linear & Abstract Algebra  15  
A group of order 6 that has no element of order 6 is isomorphic to S_3  Calculus & Beyond Homework  4  
Group of order 100 with no element of order 4?  Calculus & Beyond Homework  3  
Find the largest mass that can sit on an incline without accelerating  Introductory Physics Homework  1  
A group of order 2n conatins an element of order 2  Calculus & Beyond Homework  11 