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.

-
Great question. Thanks Mark. Amazing! – Babak S. Jun 14 '12 at 15:42

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.

-
So 255 and 65535 work. $255 = (2-1)(2+1)(2^2+1)(2^{2^2}+1)$ and 65535 has a similarly nice decomposition, and this works so neatly because $2^1-1=1$. Then we have 4,294,967,295 with 65537 as an additional factor. It looks to me as though these are the only cases where you get a complete sequence of powers of 2 starting at 1 and with no repetitions. – Mark Bennet Jun 14 '12 at 21:54

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

-

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$

-