= Solution
The $d$ distinct powers $1,a,\ldots,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 $\operatorname{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 $\varphi(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 $\varphi(d)$. Therefore
$$
m=\sum_{d\mid m}N_d\leq\sum_{d\mid m}\varphi(d)=m,
$$
using the standard divisor-sum identity for Euler's <function>. Equality forces every deficit to vanish, so $N_m=\boxed{\varphi(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}$,
$$
(h+h^{-1})^2=h^2+2+h^{-2}=2,
$$
because $h^{-2}=h^6=-h^2$. This proves \b[the stated <residue> squares to two].
Back to article page
