= Solution
The $d$ distinct powers $1,a,\ldots,a^{d-1}$ all satisfy $X^d=1$. The supplied root bound says they exhaust those roots. Thus every element of order $d$ has the form $a^n$. If $g=\gcd(n,d)$, the least positive $k$ with $a^{nk}=1$ is $d/g$, so
$$
\boxed{\operatorname{ord}_p(a^n)=\frac d{\gcd(n,d)}.}
$$
This proves both directions of the first assertion.
For existence of a <primitive root> one may apply the finite-<field> cyclicity criterion proved in the preceding section. There is also a direct counting proof: for each divisor $d$ of $p-1$, either no elements have order $d$, or the preceding argument shows there are exactly $\phi(d)$. <Lagrange's theorem for finite groups>[Lagrange's theorem] partitions all $p-1$ nonzero <residue> classes by such orders, while $\sum_{d\mid p-1}\phi(d)=p-1$. Every count is at most its corresponding $\phi(d)$, so equality of the totals forces equality at every divisor. In particular there are $\boxed{\phi(p-1)}$ <primitive roots>.
Put $t=g^{(p-1)/8}$. It has order eight, so $t^4=-1$ and $t^8=1$. The specified element is $k=t+t^7=t+t^{-1}$. Since $t^{-2}=-t^2$, squaring gives $\boxed{k^2=t^2+2+t^{-2}=2\pmod p}$.
Back to article page
