Number of elements of certain order in cyclic groups

Question

I am trying to understand a certain proof of this lemma:

Let $G$ with $|G|=n$ be a finite cyclic group. For every divisor $d$ of $n$, there are exactly $\varphi(n)$ elements of order $d$ in $G$.

The proof that I want to understand is the following:

Let $\psi(d)$ denote the number of elements of order $d$ in $G$. Let $G = \{g^{k}: k \in \mathbb{Z}_{>0} \}$ for a $g\in G$. The order of $g^k$ is $n$ if and only if $\text{gcd}(k,n)=1$. This yields $\psi(n)=\varphi(n)$. For every $d|n$ we have $g^{kd} = (g^d)^k$ being an element of order $\frac{n}{d}$. Thus $g^{kd}$ generates a cyclic group of order $\frac{n}{d}$. Hence, $$\psi\left(\frac{n}{d}\right) \geq \varphi\left(\frac{n}{d}\right) \tag{1}.$$ Moreover, $$n=\sum_{d|n}\psi(d) \geq \sum_{d|n}\phi(n))n.$$ Using (1) yields $\psi(d)=\varphi(d)$ for all $d|n$, as desired.

I am not sure how exactly equation (1) is deduced.

Answer 1

$g^d$ generates a subgroup $\langle g^d\rangle$ of order $\frac nd$. In $\langle g^d\rangle$, we have exactly $\phi(\frac nd)$ elements of order $d$ (just as there are exactly $\phi(n)$ of order $n$ in the cyclic group of order $n$). Taking into account that ther might be additional elements of order $\frac nd$ that are $\notin\langle g^d\rangle$, inequality $(1)$ follows.