 Solution

The $d$ distinct powers $1,a,\dots ,a^{d-1}$ all solve $X^d=1$. By the allowed root bound they are all its solutions. A residue $b$ of order $d$ must therefore equal $a^j$; conversely $\mathrm{ord}(a^j)=d/\gcd (d,j)$, because $d\mid jt$ characterizes the exponents $t$ with $(a^j{)}^t=1$. This proves the equivalence with $\gcd (d,j)=1$ and gives exactly $\phi (d)$ elements of order $d$ whenever any such element exists.

To establish existence at the full order too, put $m=p-1$ and let $N_d$ count elements of order $d$. By Lagrange's theorem for finite groups, these orders divide $m$. The first result gives $N_d=0$ or $\phi (d)$. Thereforeusing the standard divisor-sum identity for Euler's function. Equality forces every deficit to vanish, so $N_m=\boxed{\phi (p-1)}$.

Finally let $h=g^{(p-1)/8}$, which has order eight. Its fourth power is the unique nonidentity square root of one, namely $-1$. Since $h^7=h^{-1}$,because $h^{-2}=h^6=-h^2$. This proves the stated residue squares to two.