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?

  • 1
    $\begingroup$ Hint: what is the square of the left-hand side? What does that tell you about the possible values of the left-hand side? $\endgroup$ – Greg Martin Oct 21 '16 at 8:00
  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.