Pattern of orders of elements in a cyclic group

Solution 1:

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.$$

Solution 2:

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.

Solution 3:

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$