# Primitive Roots modulo a prime

question is as follows, and then I'll describe the headway I've made so far.

"Let p be an odd prime, and suppose that q=2p+1 is also prime. Prove that if a is incongruent to 1 and incongruent to -1 mod q, then (-a^2) is a primitive root modulo q."

My progress: I have shown that q must be congruent to 3 modulo 4. Further, I've proved previously that this means that there does not exist an integer x such that x^2 is congruent to -1 modulo q. So we have that (-a^2) CANNOT be congruent to 1 modulo q. From here, however, I am totally at a loss as to how to proceed.

All help appreciated. Thanks in advance.

-
The only possible orders of an element modulo $q$ are $1$, $2$, $p$, and $2p$; you're trying to show that the order of $-a^2$ is $2p$. You've already ruled out having order $1$. Can you rule out having order $2$ and having order $p$? (One of these at least must use the hypothesis $a\not\equiv\pm1\pmod q$....) –  Greg Martin Apr 11 at 2:05
Thank you Greg. I've since ruled out p, as follows: (-a^2)^p=-a^(2p) congruent to (-1) mod q. (final line is because 2p is simply phi(q)). –  Tom Dwan Apr 11 at 6:30
I can't seem to rule out 2 though. I realize this must use our assumption but I'm at a loss as to how to apply it. I'm likely missing something basic here. –  Tom Dwan Apr 11 at 6:30
Yes, but that happens sometimes :) The assumption on $a$ says that $-a^2\not\equiv-1\pmod q$, and $-1$ is the only element of order $2$ modulo a prime. Both halves of that sentence are a little nontrivial; see if you can confirm them! –  Greg Martin Apr 11 at 6:59
The math: $x$ having order dividing $m$ is equivalent to $x^m\equiv1\pmod q$. In particular, $x$ having order dividing $2$ is equivalent to $x^2-1\equiv0\pmod q$, or $(x-1)(x+1)\equiv0\pmod q$. Since $q$ is prime, either $x-1\equiv0$ or $x+1\equiv0$. (or use the fact that the number of roots of a polynomial modulo a prime is at most the degree) -- The intuition: the multiplicative group modulo $q$ is cyclic of order $q-1$. So the number of elements of order $m$ is the same as the number of elements of order $m$ in $\Bbb Z/(q-1)\Bbb Z$. When $m=2$, there's only one such element $(q-1)/2$. –  Greg Martin Apr 11 at 8:13