Euler function: Show that if $d|n, |\{x \in C: ord(x) = d\}| = \phi(d)$ where C is a cyclic group

Question

I'd like to show the statement in the title, where $\phi$ is the Euler function and $|C| = n$. What I already got is

$|\{x \in C: ord(x) = d\}| = |\{x \in C: |<x>| = d\}|$ and $\phi(d) = |\{x: ord(x) = d\}|$.

But I can't see why $|\{x \in C: |<x>| = d\}| = |\{x: ord(x) = d\}|$. Any hint?

Thanks a lot & have a nice weekend!

Answer 1

Let $g$ be a generator of the group $C$. For $d | n$ let us note $dd' = n$. Note that $x = g^{d'}$ has order d. The same for $x^i, 1 \leq i \leq d$, except for those $i$ for which $\gcd(d,i)>1$. So the number of elements of order d is that same as the numbers $1 \leq i \leq d$ with $\gcd(d,i) = 1$, this is (by definition) the Euler function $\Phi(d)$.