# Assuming that $r$ is a primitive root of the odd prime $p$ prove that $r^{(p-1)/2}\equiv -1 \pmod p$ holds

I know if $r$ is primitive root $r^{^{n}}\equiv a\pmod n$ from the set of residue $\{1,2,3....(n-1)\}$ but if change to $r^{(p-1)/2}\equiv -1 \pmod p$.

My assumption: It's no longer be primitive root of $p$ since the residue is $-1$ but don't know where $-1$ is come from ?

I think Euler's Criterion might related it ,that can prove $-1$ can exit. But I can't do next step. Anyone can give me a hint?

• Hint: what is the square of the left-hand side? What does that tell you about the possible values of the left-hand side? – Greg Martin Oct 21 '16 at 8:00
• Short answer: a quadratic residue cannot be a primitive root, since the order of a quadratic residue is at most $\frac{p-1}{2}<(p-1)$. It follows that every primitive root is a quadratic non-residue. – Jack D'Aurizio Oct 21 '16 at 10:14

Note that we have that $r^{p-1} \equiv 1 \pmod p$ by Fermat's Little Theorem. Then we have that: $p \mid r^{p-1} - 1 = (r^{\frac{p-1}{2}} - 1)(r^{\frac{p-1}{2}} + 1)$. Now obviously $p$ must divide one of the factors and it can't be $r^{\frac{p-1}{2}} - 1$, as then $r^{\frac{p-1}{2}} \equiv 1 \pmod p$, meaning that $r$ isn't a primitive root modulo $p$.
On the other side the fact that such a primitive root modulo $p$ exists comes from the fact that the multiplicative group modulo $p$ is cyclic.