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.

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|improve this question
1  
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? (if so, please add a (homework) tag.) –  David Kohler Mar 31 '11 at 20:30
2  
@David I have never been in a mathematics department and hence will not get mathematics homeworks :) –  Anirbit Mar 31 '11 at 20:37
1  
you don't have to be in a mathematics department to get mathematics homework :) –  David Kohler Apr 2 '11 at 23:04
add comment

2 Answers

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|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
add comment

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|improve this answer
add comment

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.