I know if rr is primitive root r^{^{n}}\equiv a\pmod nr^{^{n}}\equiv a\pmod n

from the set of residue \{1,2,3….(n-1)\}\{1,2,3….(n-1)\} but if change to r^{(p-1)/2}\equiv -1 \pmod pr^{(p-1)/2}\equiv -1 \pmod p.

My assumption: It’s no longer be primitive root of pp since the residue is -1-1

but don’t know where -1-1 is come from ?

I think Euler’s Criterion might related it ,that can prove -1-1 can exit.

But I can’t do next step. Anyone can give me a hint?

=================

1

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

2 days ago

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)\frac{p-1}{2}<(p-1). It follows that every primitive root is a quadratic non-residue. – Jack D'Aurizio 2 days ago ================= 1 Answer 1 ================= Note that we have that r^{p-1} \equiv 1 \pmod pr^{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)p \mid r^{p-1} - 1 = (r^{\frac{p-1}{2}} - 1)(r^{\frac{p-1}{2}} + 1). Now obviously pp must divide one of the factors and it can't be r^{\frac{p-1}{2}} - 1r^{\frac{p-1}{2}} - 1, as then r^{\frac{p-1}{2}} \equiv 1 \pmod pr^{\frac{p-1}{2}} \equiv 1 \pmod p, meaning that rr isn't a primitive root modulo pp. On the other side the fact that such a primitive root modulo pp exists comes from the fact that the multiplicative group modulo pp is cyclic. 1 Thank .I got it 🙂 – Fourier 2 days ago