Register to reply

Efficient way to find which element of Z*n has largest order?

by dumbQuestion
Tags: efficient, element, largest, order
Share this thread:
dumbQuestion
#1
Feb13-13, 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!
Phys.Org News Partner Science news on Phys.org
Experts defend operational earthquake forecasting, counter critiques
EU urged to convert TV frequencies to mobile broadband
Sierra Nevada freshwater runoff could drop 26 percent by 2100
AlephZero
#2
Feb13-13, 12:16 PM
Engineering
Sci Advisor
HW Helper
Thanks
P: 7,175
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.
mathwonk
#3
Feb13-13, 03:36 PM
Sci Advisor
HW Helper
mathwonk's Avatar
P: 9,488
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/844-2.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.

dumbQuestion
#4
Feb13-13, 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 pk or 2pk 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
mathwonk
#5
Feb13-13, 10:25 PM
Sci Advisor
HW Helper
mathwonk's Avatar
P: 9,488
if you look at the links i provided you will find complete proofs of these facts.
dumbQuestion
#6
Feb13-13, 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