Show $p-a^2$ is a primitive root modulo $p$ with 1 < $a$ < $p-1$

Question

Show that if $p$ is prime and $p = 2q + 1$, where $q$ is an odd prime and $a$ is a positive integer with $1 < a< p -1$, then $p - a^2$ is a primitive root modulo $p$.

I'm struggling with this one. I know the order of the primitive root has to be $2q$. I also know there are $q-1$ of them. I know $(p-a^2)^{2q} \equiv 1 \pmod{p} \Rightarrow (-a^2)^{2q} \equiv a^{4q} \equiv 1 \pmod{p}$ I know this works for all $a$ via fermats little theorem, but I dont know how to show thats actually the order. Any help or hints would be greatly appreciated

Answer 1

Let $m=2q$ be the order of the unit group modulo $p$. A unit $g$ is a primitive root if and only if $g^{m/r}\not\equiv1\pmod{p}$ for every prime divisor $r$ of $m$.

Here $r\in\{2,q\}$, so you need to have $g^q\not\equiv1\pmod{p}$, in fact $g^q\equiv-1\pmod{p}$, and $g^2\not\equiv1\pmod{p}$. The latter is easy because $p$ is prime and therefore the only solutions to $g^2\equiv 1\pmod{p}$ are $\pm1\pmod{p}$ both of which are excluded by hypothesis.

As for $g^q$ with $g = p - a^2 \equiv -a^2\pmod{p}$, we get $g^q \equiv (-a^2)^q = -a^{2q} \equiv -1\pmod{p}$, where we use the facts that $q$ is odd and that $a^m\equiv1\pmod{p}$.

Answer 2

Let $w$ be a primitive root mod $p$, i.e. a generator of the cyclic group $\mathbf F_p^*$. All the primitive roots mod $p$ are of the form $w^j$, with $j$ coprime to $p-1=2q$, with $q$ prime (by hypothesis), hence we can take $1\le j <2q, j$ odd. In particular there are exactly $q-1$ such primitive roots. It remains to characterize them in another way. Just for fun, let's proceed using quadratic residues mod $p$.

Since $\mathbf F_p^*$ is cyclic, it admits exactly one subgroup of index $2$, which is no other than the group of squares ${\mathbf F_p^*}^2$, and $\mathbf F_p^*$ is the disjoint union of ${\mathbf F_p^*}^2$ and its complement $C$, these two sets having cardinal equal to $(p-1)/2 = q$ (this means in particular that there are as many quadratic residues as non residues). Then, from what we have seen above, $C$ minus {$w^q$} is precisely the set of primitive roots mod $p$. Besides, since $(p-1)/2=q$ is odd, $-1$ is not a square, and $C=(-1){\mathbf F_p^*}^2$. This shows what we want.