A question about cyclic groups

Let $g$ be a generator of $C_n$. What is the order $g^a$?

$(g^a)^k = g^{ak} = 1$ if and only if $n|ak$. But $$\begin{align*} n|ak &\Longleftrightarrow n|ak\text{ and }a|ak\\ &\Longleftrightarrow \mathrm{lcm}(n,a)|ak\\ &\Longleftrightarrow a\left.\left(\frac{n}{\gcd(a,n)}\right) \right| ak\\ &\Longleftrightarrow \left.\frac{n}{\gcd(a,n)} \right|k \end{align*}$$ so the order of $g^a$ is exactly $\displaystyle \frac{n}{\gcd(a,n)}$.

So you are trying to count the number of integers $a$, $0\leq a \lt n$, such that $n = d\gcd(a,n)$.

Added. Alternatively, if you can show that a cyclic group of order $n$ has a unique subgroup of order $d$ when $d|n$, and no subgroups of order $d$ when $d$ does not divide $n$, then you turn the problem into finding how many generators the cyclic group of order $d$ has, which gives th result immediately.

Recall $\:g^{\large i}\:$ has order $\: n/(i,n)\ $ for a generator $\:g\:$ of $\ C_n$

Therefore $\ \ \displaystyle\ \ d\ =\ \frac{n}{(i,n)},\quad\ \ \ \ \ 0 \le i \le n$

$\quad\displaystyle\iff\quad\ (id,\ nd)\ =\ n,\ \ \ \ \ \, 0 \le i \le n$

$\quad\displaystyle\iff\quad \bigg(\frac{i\:d}{n},d\bigg)\ =\ 1,\ \ \ \ \: 0 \le i \le n,\ \ n\ |\ i\:d$

$\quad\displaystyle\iff\quad\ \ \ (\ j,\ d)\ \ =\ \ 1, \ \ \ \ \:0\le j \le d$