Suppose G is a finite cyclic group and $g\in G$ is a generator, thus $ord(g)=|G|$. Assume $|G|>1$. For any integer $n>1$, let $\phi(n)$ denote the number of elements in $\mathbb Z /n\mathbb Z^*$. Prove G contains at least $\phi(|G|)$ distinct elements h such that h generates G.

I am having a hard time figuring how to relate $\mathbb Z /n\mathbb Z^*$ using $\phi(|G|)$ as our n and being a generator of G.


HINT: There are $\phi(n)$ coprime numbers to $n$ less than $n$ and also we have that if $(k,n) = 1$, then $g^k$ also generates the group.

| cite | improve this answer | |
  • $\begingroup$ I get where you're going with this, but when we are considering $gcd(k,n)=1$, how do I tie this back to $\phi(|G|)$? Is each number the element g? If so, where do the k's come from? $\endgroup$ – RZB Oct 10 '17 at 12:32
  • $\begingroup$ @RZB, as $G$ is cyclic each element is of the form $g^k; 0 \le k <n$. So in fact $n= |G|$. Then we have that if $(k,n) = 1$, also $g^k$ is a generator of the group. The Euler totient function gives us the number of comprime numbers less than $n$ and hence the proof. $\endgroup$ – Stefan4024 Oct 10 '17 at 16:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.