Let $d$ such that $d|p-1$ and $p$ prime. If $\psi(d)$ is the number of elements of order $d $. Show that $\sum_{c|d}\psi(c)=d$

Question

Let $d$ be a natural number and $p$ be a prime such that $d|p-1$. We let $\psi(d)$ denote the number of elements in $\mathbb{F}^*_p$ with order $d$. I tried solve this exercise using the fact that $$\#\{x \in \mathbb{F}^*_p:x^d\equiv1 [p]\}=d$$ But i don't know how to conclude. I would like to relate this to $$\sum_{c|d}\psi(c)$$ Somehow.\ I've not seen a proof using this method but i remember seeing it somewhere.

Answer 1

You were on the right track. Those $d$ elements $x$ for which $x^d\equiv1\pmod p$ form a cyclic subgroup of the multiplicative group modulo $p$. Thus the order of each of them is a divisor of $d$. Conversely, an element whose order is a divisor of $d$ satisfies $x^d\equiv1\pmod p$. Thus these $d$ elements are precisely the ones whose orders divide $d$.