If $\left\langle a^k \right\rangle =\mathbb Z _n ^{\times } $ $\forall k $: $\gcd (k,n)=1 $, can there be other generators? Given that $a $ generates the group $\mathbb Z _n ^{\times } $, where $\mathbb Z _n ^{\times } $ is the set of all $a \in \mathbb Z _n $ such that $\gcd(a,n)=1 $ and the operation is multiplication, I can show that for every $k $ such that $\gcd(k,n)=1 $, $a ^k $ also generates $\mathbb Z _n ^{\times } $.
There are $\phi (n) $ such generators. Can there be other generators of $\mathbb Z _n ^{\times } $?
Thanks in advance!
 A: You seem to be mixing two groups:


*

*$\mathbb Z _n = \mathbb Z/n\mathbb Z$ is a cyclic additive group of order $n$ generated by any $a\in \mathbb Z$ with $\gcd(a,n)=1$. There are exactly $\phi(n)$ generators.

*$\mathbb Z _n ^{\times }$ is a multiplicative group of order $\phi(n)$, formed by the set of $a$ such that $\gcd(a,n)=1$. However, $\mathbb Z _n ^{\times }$ is not always cyclic. If $a$ is a generator of $\mathbb Z _n ^{\times }$, then $a^k$ is also a generator if $\gcd(k,\phi(n))=1$. There are $\phi(\phi(n))$ generators.
The general result is that if $G$ is a cyclic group of order $m$ and $g$ is a generator of $G$, then all generators are of the form $g^k$ with  $\gcd(a,m)=1$. There are therefore exactly $\phi(m)$ generators. More generally, the order of $a^k$ is $\frac{m}{\gcd(k,m)}$.
A: In classic number-theoretic language, if $n$ hs a primitive root, then $n$ has $\varphi(\varphi(n))$ primitive roots. 
I assume you know how to prove that if $g$ is a primitive root of $n$, then $g^k$ is a primitive root of $n$ for any $k$ relatively prime to $\varphi(n)$. One uses the fact that there exist integers $x$ and $y$ such that $kx+\varphi(n)y=1$. 
For the other direction, suppose that $\gcd(k,\varphi(n))=d\gt 1$. Then $k\cdot\frac{\varphi(n)}{d}$ is a multiple of $\varphi(n)$. It follows that $(g^k)^{\varphi(n)/d}\equiv 1\pmod{n}$, so $g^k$ has order $\lt \varphi(n)$, and therefore is not a primitive root of $n$.  
