MHB Primitive Roots Modulo $p$: The $(p-1)/2$ Rule

[alexmahone]

Is it true that $g$ is a primitive root modulo $p$ if and only if $g^{(p-1)/2} \equiv -1 \pmod p$?

 

[Opalg]

Is it true that $g$ is a primitive root modulo $p$ if and only if $g^{(p-1)/2} \equiv -1 \pmod p$?

No. For example, take $p=7$ and $g=6$. The congruence is satisfied, but $6$ is not a primitive root$\mod 7$.

 

[I like Serena]

Is it true that $g$ is a primitive root modulo $p$ if and only if $g^{(p-1)/2} \equiv -1 \pmod p$?

Hi Alexmahone,

I assume that $p$ is supposed to be an odd prime?

If so, then it is true that $g$ is a primitive root modulo $p$ if and only if the order of $g$ is $p-1$ modulo $p$.

So what we need is that the order of $g$ is $p-1$.
From $g^{(p-1)/2} \equiv -1 \pmod p$, we can only conclude that the order of $g$ is not $(p-1)/2$, but it could still be $(p-1)/3$ or some such.

Opalg's example is showing exactly that, which is the simplest counter example. He picked the smallest odd prime for which $(p-1)/k$ is an integer with $k>2$, and he found a $g$ to match. :)