# When $d \mid n$, the number of elements of order $d$ in a cyclic subgroup of order $n$ is $\phi (d)$

If $d$ is a positive divisor of $n$, the number of elements of order $d$ in a cyclic subgroup of order $n$ is $\phi (d)$=the number of positive natural numbers less than $d$ which are coprime to $d$.

The question I have concerns a part of the proof:

If $d | n$ then there exists exactly one subgroup of order $d$ -- call it $\langle a \rangle$. Then every element of order $d$ also generates the subgroup $\langle a \rangle$ and an element $a^k$ generates $\langle a \rangle$ iff $gcd(k,d) = 1$ implies that the number of such elements is precisely $\phi (d)$.

How does every element of order $d$ also generate the subgroup $\langle a \rangle$, wouldn't it be only one $a$ since $|\langle a \rangle| = |a|$? And how does this fact imply $\phi(d)$ is the correct number?

Consider $\mathbb{Z}_5$. Under addition we have $$\mathbb{Z}_5=\langle 1 \rangle=\langle 2 \rangle=\langle 3 \rangle=\langle 4 \rangle$$

A cyclic group has at least one generator, but if it is finite, then it will have exactly $\phi (n)$ total, where $G$ is your cyclic group and $n=\left| G \right|$. So equivalently, you could define the finite cyclic group of order $n$ as the group with exactly $\phi(n)$ generators, but it would need to be proven that this is equivalent to being generated by a single element.

• But why does every element of order $d$ generate the subgroup $\langle a \rangle$? I know that $|\langle a \rangle | = |a| = d$, but doesn't this imply that only one element generates $\langle a \rangle$? – Oliver G Jul 12 '16 at 18:12
• No, $|\langle a \rangle |=|a|=d$ just implies that it is generated by at least one element; namely $a$. If $|b|=d$ for $b \in \langle a \rangle$, where $|\langle a \rangle |=d$, then $b$ must generate all the elements of $\langle a \rangle$, because $\langle a \rangle$ only has $d$ elements. If $\langle b \rangle$ generates exactly $d$ elements, then it must generate all the elements. Remember $b^r \in \langle a \rangle$ – JasonM Jul 12 '16 at 18:21

An element of order d generated a subgroup of order d which is $<a>$ since $<a>$ is unique.

A subgroup of order $d$ is isomorphic to $Z/d$ if $[n]$ generates $Z/d$, $=m[n]$ this is equivalent to saying $1=mn+cd$, thus $gcd(d,n)=1$. Thus there exists $\phi(d)$ generators.

• So $a$ generated the subgroup $\langle a \rangle$, therefore there is only one element whose order is $d$? – Oliver G Jul 12 '16 at 17:35
• I suppose you have understood that there is only one subgroup of order d – Tsemo Aristide Jul 12 '16 at 17:36
• A subgroup of $Z/n$ of order $d$ is generated by $[n/d]$. – Tsemo Aristide Jul 12 '16 at 17:39
• But the proposition is saying that the number of elements of order $d$ is $\phi (d)$, which isn't always $1$, so how can there be only one element that has order $d$ that generates $\langle a \rangle$? – Oliver G Jul 12 '16 at 17:39