[Math] Amount of generators for cyclic group and Euler’s function

abstract-algebraelementary-number-theory

I have this question, since I'm confused about this concept. Let's say I have a cyclic group, for example $\mathbb{Z}_7^{\times} = \left\{1, 2, 3, 4, 5, 6\right\}$. What is the relationship between the amount of generators for this group and $\phi(7)$, with $\phi$ Euler's function?

I found the generators as $\left\{3, 4, 5, 6 \right\}$. I know that if $G$ is a cyclic group of order $n$, and $g$ is a generator, then $g^s$ will also be a generator if and only if $gcd(s,n) = 1$. But then I read somewhere that if $n$ is prime (which in our case it is), then $\phi(7) = 6$ and the amount of generators should be $6$? This cannot be true for the group $\mathbb{Z}_7^{\times}$, since $1$ cannot possibly be a generator for multiplication.

For example, if I have the cyclic group $\mathbb{Z}_{13}^{\times}$, what is the best method to find a generator, and to find how many there are?

Best Answer

A cyclic group with $n$ elements has $\varphi(n)$ generators.

It seems like what you're getting confused by is that:

  • The group $\mathbb{Z}_7^\times=\{1,2,3,4,5,6\}$ is a cyclic group with 6 elements, and therefore it should considered equivalent to (more precisely, it is isomorphic to) the cyclic group $\mathbb{Z}_6$, and you should expect $\varphi(6)=2$ generators, not $\varphi(7)=6$ generators

  • The elements $4$ and $6$ in $\mathbb{Z}_7^\times$ are not generators: the powers of $4$ in $\mathbb{Z}_7^\times$ are $\{1,4,2\}$, and the powers of $6$ in $\mathbb{Z}_7^\times$ are $\{1,6\}$. (The only generators of $\mathbb{Z}_7^\times$ are $3$ and $5$, and there are exactly $2=\varphi(6)$ of them.)

More generally, if $p$ is a prime number, then $\mathbb{Z}_p$ is a cyclic group with $p$ elements, while $\mathbb{Z}_p^\times$ is a cyclic group with $p-1$ elements, so $\mathbb{Z}_p^\times$ has $\varphi(p-1)$ generators.

As for the best method to find a generator, that is a far more advanced problem.