Past exam of the Probability, statistics and options II course of the University of Oxford / 2008 / C / 2 / Solution

The $d$ distinct powers $1,a,\dots ,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$, soThis 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 $\varphi (d)$. Lagrange's theorem partitions all $p-1$ nonzero residue classes by such orders, while ${\sum }_{d\mid p-1}\varphi (d)=p-1$. Every count is at most its corresponding $\varphi (d)$, so equality of the totals forces equality at every divisor. In particular there are $\boxed{\varphi (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(\mathrm{mod}p)}$.