5
$\begingroup$

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)

  • 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?2011-03-31
  • 2
    @David I have never been in a mathematics department and hence will not get mathematics homeworks :)2011-03-31
  • 1
    you don't have to be in a mathematics department to get mathematics homework :)2011-04-02

2 Answers 2

2

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$

  • 0
    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$)2011-04-06
  • 0
    @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\:.$2011-04-06
2

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.