# $h^{\frac{p-1}{2}} \equiv 1 \bmod p$ and $g^x \equiv h \bmod p$ for a primitive root $g$ $\iff$ $x$ is even

Let $g$ be a primitive root for the odd prime $p.$ Suppose $g^x \equiv h \pmod p$. Show that $x$ is even if $h^{\frac{p-1}{2}} \equiv 1\pmod p$ and $x$ is odd if $h^{\frac{p-1}{2}}\equiv -1\pmod p$.

If $g^{x(p-1)/2} = 1$ then by Eulers theorem we must have $(p-1) | x(p-1)/2$ which is only possible if x is even. On the other hand if $g^{x(p-1)/2} = -1$ then also $g^{(p-1)/2} = -1$, dividing gives $g^{x(p-1)/2} /g^{(p-1)/2} = 1$ or $g^{(x-1)(p-1)/2} =1$. Again from Euler we must have $(p-1)|(x-1)(p-1)/2$ which is only possible if x is odd.
$x$ is even if and only if $g^x$ is a nonzero quadratic residue, i.e. $\binom{g^x}{p}=1$. The claim follows from the well known fact that, for all integers $x$, $$\binom{x}{p} \equiv x^{\frac{1}{2}(p-1)}\pmod{p}.$$
• We have a "if and only if". Hence, $x$ is odd iff $g^x$ is a nonzero nonquadratic residue iff $\binom{g^x}{p}=-1$. – Paolo Leonetti Oct 10 '16 at 17:57