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

  • #1
125
0
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!
 

Answers and Replies

  • #2
AlephZero
Science Advisor
Homework Helper
6,994
293
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
mathwonk
Science Advisor
Homework Helper
2020 Award
11,154
1,349
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 [Broken]

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.
 
Last edited by a moderator:
  • #4
125
0
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
 
  • #5
mathwonk
Science Advisor
Homework Helper
2020 Award
11,154
1,349
if you look at the links i provided you will find complete proofs of these facts.
 
  • #6
125
0
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!
 

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

Replies
15
Views
8K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
13
Views
419
Replies
5
Views
3K
Replies
8
Views
9K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
10
Views
6K
Top