Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How does one see that the cyclic group $C_n$ of order $n$ has $\phi(d)$ elements of order $d$ for each divisor $d$ of $n$?

(where $\phi(d)$ is the Euler totient function)

share|cite|improve this question
I think a good hint is to start from the definitions. A group is cyclic if it can be generated from one element. Now playing with that element, you should be able to compute the order of any other element. Also, is that a homework? – David Kohler Mar 31 '11 at 20:30
@David I have never been in a mathematics department and hence will not get mathematics homeworks :) – Anirbit Mar 31 '11 at 20:37
you don't have to be in a mathematics department to get mathematics homework :) – David Kohler Apr 2 '11 at 23:04
up vote 1 down vote accepted

Recall $\rm\:g^i\:$ has order $\rm\: n/(i,n)\ $ for a generator $\rm\:g\:$ of $\rm\ C_n\:.$

Therefore $\rm\ \ \displaystyle\ \ d\ =\ \frac{n}{(i,n)},\quad\ \ 0 \le i \le n$

$\rm\quad\displaystyle\iff\quad\ \ \ (i\:d,\ nd)\ =\ n,\ \ \ \ 0 \le i \le n$

$\rm\quad\displaystyle\iff\quad \bigg(\frac{i\:d}{n},d\bigg)\ =\ 1,\ \ \ \ \: 0 \le i \le n,\ \ n\ |\ i\:d$

$\rm\quad\displaystyle\iff\quad\quad\ (\ j,\ d)\ \ =\ \ 1, \ \ \ \ \:0\le j \le d$

share|cite|improve this answer
Sorry. I am a bit confused about your argument. Are you saying that there is a one-to-one correspondence between the $j's$ that solve $(j,d) =1$ and $i's$ that solve $n = d(i,n)$ ? (I guess that the set of $j's$ is typically very different from the set of $i's$) – Anirbit Apr 6 '11 at 18:31
@Anirbit: Yes, that's what the above equivalences show. Note that $\rm\ j\ =\ i\:d/n\ $ above. The equivalences prove that the $\rm\:g^i\:$ has order $\rm\:d\:$ iff $\rm\:(j,d)= 1\:,\ 0\le j\le d\:.$ As is well-known, there are precisely $\rm\:phi(d)\:$ such $\rm\:j\:.$ – Bill Dubuque Apr 6 '11 at 18:43

Let $g$ be a generator of $C_n$. What is the order $g^a$?

$(g^a)^k = g^{ak} = 1$ if and only if $n|ak$. But $$\begin{align*} n|ak &\Longleftrightarrow n|ak\text{ and }a|ak\\ &\Longleftrightarrow \mathrm{lcm}(n,a)|ak\\ &\Longleftrightarrow a\left.\left(\frac{n}{\gcd(a,n)}\right) \right| ak\\ &\Longleftrightarrow \left.\frac{n}{\gcd(a,n)} \right|k \end{align*}$$ so the order of $g^a$ is exactly $\displaystyle \frac{n}{\gcd(a,n)}$.

So you are trying to count the number of integers $a$, $0\leq a \lt n$, such that $n = d\gcd(a,n)$.

Added. Alternatively, if you can show that a cyclic group of order $n$ has a unique subgroup of order $d$ when $d|n$, and no subgroups of order $d$ when $d$ does not divide $n$, then you turn the problem into finding how many generators the cyclic group of order $d$ has, which gives th result immediately.

share|cite|improve this answer

Your Answer


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.