A cyclic group $C_n$ of order $n$ has $\phi(d)$ elements of order $d$ for each divisor $d$ of $n$ How does one see that the cyclic group $C_n$ of order $n$ has $\phi(d)$ elements of order $d$ for each divisor $d$ of $n$? 
(where $\phi(d)$ is the Euler totient function) 
 A: 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.
A: Recall $g^{\large i}$ has order $\: n/(i,n)\ $ for a generator $\:g\:$ of $\ C_n\,$ (or,  additively in isomorphic group $\Bbb Z_n\,$ $ $ recall $\,\ i\ \,$ has order $\,n/(i,n),\,$ i.e. $\,k\cdot i\equiv 0\pmod{\!n}\iff n\mid ki\iff n/(i,n)\mid k)$
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$
where we used the gcd distributive law above.
