Pattern of orders of elements in a cyclic group Doodling as I was contemplating another recent question, I picked out the orders of elements of the cyclic group $Z_{15}$ namely:
1 element of order 1
2 elements of order 3
4 elements of order 5
8 elements of order 15
In a group of order 3 you have 1 element of order 1 and two elements of order 3.
Are there other examples of this same pattern (powers of 2), and can anyone show and prove a general rule.
 A: The number of elements of order $d$, where $d$ is a divisor of $n$, is $\varphi(d)$.
These values of $\varphi(d)$ are powers of $2$ for all divisors $d$ of $n$ precisely when $n$ is a power of $2$ times a product of distinct Fermat primes, that is, primes of the form $2^{2^k}+1$.  The power of $2$ may be $2^0$, and the product may be the empty one.
The proof is immediate from the usual formula for $\varphi$ in terms of the prime power factorization.  
So the answer is essentially the same as the classical one of which regular polygons are Euclidean-constructible. Sadly, there are not many Fermat primes known.
At this time, we only have $3$, $5$, $17$, $257$, and $65537$ to play with.
A: Here's te easiest pattern I know
For any cyclic group $\mathbb{Z}_n \cong \left<a\right>$ for some $a$ with order $n$
Then $\left<a\right>=\{a^k \mid k=1 \ldots n \}$ and the order
$\left|a^k\right|=\frac{n}{\text{gcd}(k,n)}$ for $k=1\ldots n$
A: Let $G$ be a cyclic group of order $n$, and let $a\in G$ be a generator. Let $d$ be a divisor of $n$. 
Certainly, $a^{n/d}$ is an element of $G$ of order $d$ (in other words, $\langle a^{n/d}\rangle$ is a subgroup of $G$ of order $d$). If $a^t\in G$ is an element of order $d$, then $a^{td}=e$, hence $n\mid td$, and thus $\frac{n}{d}\mid t$. This shows that $a^t\in \langle a^{n/d}\rangle$, and thus $\langle a^t\rangle=\langle a^{n/d}\rangle$ (since they are both subgroups of order $d$). Thus, there is exactly one subgroup, let's call it $H_d$, of $G$ of order $d$, for each divisor $d$ of $n$, and all of these subgroups are themselves cyclic. 
Any cyclic group of order $d$ has $\phi(d)$ generators, i.e. there are $\phi(d)$ elements of order $d$ in $H_d$, and hence there are $\phi(d)$ elements of order $d$ in $G$. Here, $\phi$ is Euler's phi function.
This can be checked to make sense via the identity
$$\sum_{d\mid n}\phi(d)=n.$$
