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.