Prove that exactly $\phi(d)$ elements have order $d$ [duplicate]

Let $p$ be a prime number. Prove that among $1,2,\ldots,p-1,$ exactly $\phi(d)$ elements have order $d$, given that $d \mid (p-1)$. (Note: Here $\phi(d)$ denotes Euler's Totient Function.)

I didn't see a way of proving this statement. How can we count solutions $k$ to $k^d \equiv 1 \pmod{p}$?

Solution 1:

Let $g$ be the primitive root modulo $p$ then $\text{ord}_p(g)=\varphi(p)=p-1$ and $\{ g,g^2, \cdots , g^{p-1} \}$ is a reduced residue system modulo $p$. Hence, it suffices to find number of $l$ so that $g^{dl} \equiv 1 \pmod{p}$ and $\text{ord}_p(g^l)=d$. We know that $\text{ord}_p(g)=p-1$ so we need to find number of $1 \le l \le p$ so that $p-1 \mid ld$ and $\gcd \left( \dfrac{ld}{p-1},d \right)=1$.

Note that we need the second condition, because otherwise if $\gcd \left( \dfrac{ld}{p-1},d \right)=r>1$ then $(g^l)^{d/r} \equiv 1 \pmod{p}$, a contradiction since $\text{ord}_p(g^l)=d$.

Thus, it suffices to find $x=\dfrac{ld}{p-1}$ so that $\gcd (x,d)=1$ or $1 \le x \le d$ so $\gcd (x,d)=1$. Thus, there are $\varphi(d)$ solutions for $x$ which means $\varphi(d)$ solutions for $l$ or $\varphi(d)$ solutions for $k$.