A cyclic group $C_n$ of order $n$ has $\phi(d)$ elements of order $d$ for each divisor $d$ of $n$

$\begingroup$ I think a good hint is to start from the definitions. A group is cyclic if it can be generated from one element. Now playing with that element, you should be able to compute the order of any other element. Also, is that a homework? $\endgroup$

$\begingroup$ @David I have never been in a mathematics department and hence will not get mathematics homeworks :) $\endgroup$

$\begingroup$ you don't have to be in a mathematics department to get mathematics homework :) $\endgroup$

2 Answers 2

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

$(g^a)^k = g^ = 1$ if and only if $n|ak$. But $$\begin n|ak &\Longleftrightarrow n|ak\text< and >a|ak\\ &\Longleftrightarrow \mathrm(n,a)|ak\\ &\Longleftrightarrow a\left.\left(\frac<\gcd(a,n)>\right) \right| ak\\ &\Longleftrightarrow \left.\frac <\gcd(a,n)>\right|k \end$$ so the order of $g^a$ is exactly $\displaystyle \frac<\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.