Prove that exactly $\varphi (d)$ residues have order $d$ modulo $p$

Question

Prove that exactly $\varphi (d)$ residues have order $d$ modulo $p$ for all $d \mid \varphi(p)$ where $p$ is prime.

I was wondering if there was a way to solve this using number theory and not group theory. Here was the start of my attempt:

Let $g$ be a primitive root modulo $p$, so that $\text{ord}_p(g) = \varphi(p) = p-1$ and $\{g,g^2,\ldots,g^{p-1}\}$ is the complete residue system modulo $p$. It suffices to find the number of $m$ such that $\text{ord}_p(g^m) = d$.

We know that $g^{dm} = g^{(p-1) \cdot \frac{dm}{p-1}}$.

How do we continue from here?

Answer 1

If $d \mid \phi(p)$ then write $d'$ for the number such that $dd' = \phi(p)$. Now $h = g^{d'}$ has order $d$ (if $h^k = 1$ for $k<d $ then $g^{d'k} = 1$ with $d'k < \phi(p)$ and $g$ isn't a primitive root). We have that $h^m$ also has order $d \iff \gcd(m,d)=1$. We now have $\phi(d)$ elements of order $d$. These are the only ones: Let $g^k$ be of order $d$ then $g^{kd} = 1$ thus $\phi(p)=d'd\mid kd$, so $d'|k$ and $g^k$ is a power of $h$ of order $d$.