Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Great question. Thanks Mark. Amazing! –  Babak S. Jun 14 '12 at 15:42

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
    
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.$$

share|improve this answer

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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.