Distinct generators of a finite cyclic group.

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.
• 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? – RZB Oct 10 '17 at 12:32
• @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. – Stefan4024 Oct 10 '17 at 16:44