# Number of elements of certain order in cyclic groups

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.

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