Prove if $n$ has a primitive root, then it has exactly $\phi(\phi(n))$ of them

Prove if $n$ has a primitive root, then it has exactly $\phi(\phi(n))$ of them.

Let $a$ be the primitive root then I know other primitive roots will be among $\{a,a^2,a^3 \cdots\cdots a^{\phi(n)} \}$ because any other number will be congruent modulo $n$ to one of these. Then I figured as the answer is $\phi(\phi(n))$ so for $a^k$ to be primitive root, $k$ must be coprime with $\phi(n)$.But I don't know the reason.Am I missing any silly point?

Hint: If $G$ is a cyclic group of order $n$ generated by an element $g$, then the order of the element $g^m$ is $n/\gcd(m,n)$ (you should have seen this result shortly after cyclic groups were introduced). In particular $g^m$ is of order $n$, if and only if $\gcd(m,n)=1$.

As you pointed out, if $g$ is a primitive root of $n \ge 3$, then the primitive roots must be among $g, g^2, \dots, g^{\varphi(n)-1}$.

To count the exact number, as you observed, we need to show that for $1 \le k \le\varphi(n)-1$, $g^k$ is a primitive root iff $k$ is relatively prime to $\varphi(n)$.

Suppose that $k$ is relatively prime to $\varphi(n)$. Then there exist integers $x$ and $y$ such that $xk=y\varphi(n)+1$. It follows that $(g^k)^x=(g^{\varphi(n)})^y g\equiv g\pmod{n}$. Since $g^{kx}\equiv g\pmod{n}$, for any $e$ we have $$g^e\equiv (g^{kx})^e\equiv (g^k)^{xe}\pmod{n}.$$ It follows that any power of $g$ is congruent to some power of $g^k$. This implies that $g^k$ is a primitive root of $n$.

On the other hand, if $k$ is not relatively prime to $\varphi(n)$, let $d \gt 1$ be a common divisor. Then $(g^k)^{\varphi(n)/d}\equiv 1\pmod{n}$, since $k\varphi(n)/d$ is a multiple of $\varphi(n)$. It follows that $g^k$ has order $\le \varphi(n)/d$, so cannot be a primitive root.

For $a^k$ to be a primitive root, you have to show that $1,a^k,a^{2k},\dots,a^{(\phi(n)-1)k}$ are different (modulo $n$). So, show that if $\gcd(k,\phi(n))\ne1$ then these numbers aren't different (easiest way is by showing 1 is repeated), and show that if the gcd is 1 then the numbers are all distinct.

If $a^k$ is primitive, then for any $m$ we have some $t$ such that $a^m=(a^k)^t=a^{tk}$, thus $tk\equiv m\mod \phi(n)$. If $k$ and $\phi(n)$ had gcd $c$, then $m=t(k/c)c+x(\phi(n)/c)c$ for some $t,x$ hence is divisible by $c$. If we let $m=1$ we get that $c=1$, thus $k$ and $\phi(n)$ are coprime.

On the other hand, if $k$ and $\phi(n)$ are coprime then we have some $t$ such that $tk\equiv 1\mod \phi(n)$, so for any $m$ we have $mtk\equiv m\mod \phi(n)$ thus $(a^k)^{mt}=a^m$. Hence $a^k$ is a primitive root.

Thus there is a bijection between the set of primitive roots and the set of positive integers less than $\phi(n)$ and coprime to it, of which there are $\phi(\phi(n))$. Thus there are $\phi(\phi(n))$ primitive roots.