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
    you don't have to be in a mathematics department to get mathematics homework :)2011-04-02

2 Answers 2

2

Recall $\:g^{\large i}\:$ has order $\: n/(i,n)\ $ for a generator $\:g\:$ of $\ C_n$

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

$\quad\displaystyle\iff\quad\ (id,\ nd)\ =\ n,\ \ \ \ \ \, 0 \le i \le n$

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

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

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