Count elements in a cyclic group of given order

First we note a few things about a cyclic group $G$ of order $n$:

• There is an element in $G$ of order $k$ iff $k\mid n$.
• Taking an element $b\in G$ of order $k$, all other elements of $G$ of order $k$ are contained in $\langle b \rangle$.

From this, we may conclude that we need only to focus on the number of elements of order $n$. Why? Because for any other order $k$, either $k \nmid n$ and there are zero elements of that order, or $k \mid n$, and there is an element $b$ of order $k$, and we can just look at the group $\langle b \rangle$.

Finally, given your $a \in G$ as a generator for the group, what is the criterion that $a^m$ is a generator for $G$, i.e. that $O(a^m) = n$? Going by your formula, that would be when $\gcd(m, n) = 1$. How many such numbers are there? Fortunately, that's a question that's been pondered before, and the answer is called $\phi(n)$.

(This means that if you have some $k\mid n$ instead, you get the answer by applying the above to the group $\langle b\rangle$, which gives $\phi(k)$.)

All subgroups of cyclic groups are cyclic. In fact, a cyclic group $G$ of order $N$ contains exactly one cyclic subgroup of order $d$ for every divisor $d$ of $N$. Thus the order of every element in $G$ must divide the order of $G$.

Now suppose $d$ divides $N$, the question is how many elements of $G$ have order $d$? This question is equivalent to the question, how many generators of the unique subgroup of $G$ of order $d$ are there?

Here it helps to remember that $G\cong\mathbb{Z}/N\mathbb{Z}$, and that the subgroup we are thinking about is just $\mathbb{Z}/d\mathbb{Z}$. The number of generators of this group is exactly $\phi(d)$, where $\phi$ is the Euler totient function. Equivalently, this is the order of the multiplicative group $(\mathbb{Z}/d\mathbb{Z})^*$. Also equivalently, this is the number of integers between $1$ and $d-1$ that are coprime to $d$.

The Euler totient function is really the function you want to think about, and gives you the answer to your question. If you want to know more about any of the concepts involved here, please reply!