Does Z*(n) always have a generator?

  • Thread starter dumbQuestion
  • Start date
  • Tags
    Generator
In summary: The order of an element a in a cyclic group can be determined by the Euler totient function, \varphi(t). This function takes a positive integer and returns the number of elements in the group such that the product of the orders of the two elements is 1. For example, \varphi(5) would return 2 because there are two elements in the group with orders 5 and 2, and the order of 1 is not a factor of 5.
  • #1
dumbQuestion
125
0
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?
 
Physics news on Phys.org
  • #2
dumbQuestion said:
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)

A cyclic group is by definition a group with a generator.

Is there a theorem that says Z*(n) is cyclic?

No, because it's not true. Take [itex]\mathbb{Z}^*(8)=\{1,3,5,7\}[/itex]. Then we have that [itex]3^2=5^2=7^2=1[/itex]. So there is no generator.

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/5...multiplicative-subgroups-of-fields-are-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?

If you have a cyclic group of order k, let's say [itex]\{e,g,g^2,...,g^k\}[/itex]. Then one can prove that the order of an element [itex]g^t[/itex]is equal to [itex]\frac{k}{gcd(k,t)}[/itex]. So the number of generators of the group is equal to the number of t such that [itex]gcd(k,t)=1[/itex]. This number is denoted by [itex]\varphi(t)-1[/itex] and is called the Euler totient function.

In the case of [itex]\mathbb{Z}^*(n)[/itex]. If n is a prime, then this is cyclic with order n-1. So the number of generators is given by [itex]\varphi(n-1)-1[/itex].
http://en.wikipedia.org/wiki/Euler's_totient_function
 
  • #3
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
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 that's 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
dumbQuestion said:
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 that's 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.

OK, but I'm working in the cyclic groups [itex]\{1,g,g^2,...,g^{k-1}\}[/itex]. So I have that [itex]1=g^0[/itex], so t=0. So the order of 1 is [itex]k/gcd(k,0)[/itex]. It might not be very easy to see what gcd(k,0) is though. But we can also write [itex]1=g^k[/itex]. This makes it easier because then t=0 and the order is [itex]k/gcd(k,k)=k/k=1[/itex]. Like expected.

This actually implies that the right definition of gcd(k,0) would be gcd(k,0)=k.
 
  • #6
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?
 

1. What is Z*(n)?

Z*(n) is the set of all integers that are relatively prime to n. In other words, it is the set of positive integers less than n that have no common factors with n.

2. What is a generator in Z*(n)?

A generator in Z*(n) is an element that, when raised to different powers, produces all the elements in the set. In other words, it is an element that generates all the other elements in the set through multiplication.

3. Does Z*(n) always have a generator?

No, Z*(n) does not always have a generator. It only has a generator if n is a prime number or a power of a prime number. In other words, there must exist at least one element in Z*(n) that generates all the other elements in the set.

4. How can I find a generator in Z*(n)?

To find a generator in Z*(n), you can use the primitive root theorem. This theorem states that if n is a prime number, then there exists at least one primitive root, which is a generator in Z*(n). If n is not a prime number, you can factorize it into its prime factors and find generators for each prime factor. The least common multiple of these generators will then be a generator for Z*(n).

5. Why is it important to determine if Z*(n) has a generator?

Determining if Z*(n) has a generator is important because it has many practical applications, especially in cryptography. For example, the Diffie-Hellman key exchange algorithm relies on the existence of a generator in Z*(n). It is also useful in finding solutions to certain mathematical problems, such as the discrete logarithm problem.

Similar threads

  • Linear and Abstract Algebra
Replies
1
Views
622
  • Linear and Abstract Algebra
Replies
11
Views
1K
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
8
Views
664
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
7
Views
4K
  • Linear and Abstract Algebra
Replies
14
Views
2K
  • Linear and Abstract Algebra
Replies
5
Views
2K
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
3
Views
1K
Back
Top