---- > [!theorem] Theorem. ([[number of elements of each order in a cyclic group]]) > Let $G \cong C_{n}$. If $d | n$, then the number of elements in $G$ of [[order of an element in a group|order]] $d$ is $\phi(d)$, where $\phi$ denotes the [[Euler phi function]]. And $\sum_{d | n}^{}\phi(d)=n.$ ^4608aa > [!proof]- Proof. ([[number of elements of each order in a cyclic group]]) > Let $d$ be such that $d$ [[divides]] $n$. Then [[uniqueness of subgroups of finite cyclic groups|G has a unique subgroup of order d]], $K_{d}$, and that [[subgroup]] is [[cyclic group|cyclic]]. Due to said uniqueness, an element $a^{i}$ in $G$ has [[order of an element in a group|order]] $d$ if and only if it [[generating set of a group|generates]] $K_{d}$. By [[order of element in cyclic group]], we know that, in general, $|a^{i}|=\frac{d}{\text{gcd}(i,d)}$. Hence in order for $a^{i}$ to [[generating set of a group|generate]] $K_{d}$, we need $a^{i}=d$, i.e., $\text{gcd}(i,d)=1$. Thus, the number of elements of order $d$ is $|\{ a^{i} : 1 \leq i \leq n , \text{gcd}(i,d)=1\}|=|\{ i:1 \leq i \leq n, \text{gcd}(i,d)=1 \}|=\phi(d)$. This is what we wanted to show for the first part. \ For the second part, we define an [[equivalen[](uniqueness%20of%20subgroups%20of%20finite%20cyclic%20groups.md): we declare $a \sim b$ if $|a|=|b|$. Clearly: >- (reflexivity) $|a|=|a|$ so $a \sim a$ for all $a \in G$ >- (symmetry) $|a|=|b| \iff |b|=|a|$ for $a \sim b$ $\implies$ $b \sim a$ for all $a,b \in G$; >- (transitivity) $|a|=|b|$ and $|b|=|c|$ implies $|a|=|c|$, hence $a\sim b \sim c$. \ By [[partitions are always determined uniquely by equivalence relations]], the [[equivalence class|equivalence classes]] of $\sim$ [[partition]] $G$. A given [[equivalence class|equivalence class]] correspond to sets of elements of a given [[order of an element in a group|order]] $d$; hence that class's size is precisely $\phi(d)$. Of course, the element has order $d$ for $d \not{|}n$, by [[Lagrange's Theorem]]. Thus $\sum_{j=1}^{n} \text{number of groups of order }j=\sum_{d | n}^{} \text{number of groups of order }d=\sum_{d | n}^{}\phi(d).$ ^6894e6 ---- #### ----- #### References > [!backlink] > ```dataview TABLE rows.file.link as "Further Reading" FROM [[]] FLATTEN file.tags GROUP BY file.tags as Tag > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```