Given a prime $p = 2^n+1$, show that $\alpha^{(p-1)/2} \equiv -1 \pmod p$

Question

This is from a paper by Pohlig and Hellman where they describe an improved discrete log algorithm. While describing the algorithm, they use the following equivalence:

$$\alpha^{(p-1)/2} \equiv -1 \pmod p$$

Where $p = 2^n+1$ is a prime and $\alpha$ is a primitive element of $\mathbb{Z}_p^*$. But why is this true?

My reasoning: from Euler's theorem, $\alpha^{\phi(p)} = \alpha^{p-1} \equiv 1 \pmod p$, so $\alpha^{(p-1)/2} \equiv 1^{1/2} \equiv 1 \pmod p$

Answer 1

Because we are assuming that $\alpha$ is a primitive element modulo $p$. That means that no two numbers from the set $\{1,\alpha,\alpha^2,\ldots,\alpha^{p-2}\}$ are congruent modulo $p$. But if we had $\alpha^{\frac{p-1}2}\equiv1\pmod p$, this would not happen. Therefore, and since $\alpha^{\frac{p-1}2}\equiv\pm1\pmod p$, the conclusion is that $\alpha^{\frac{p-1}2}\equiv-1\pmod p$.

Answer 2

Here's another proof. By Euler's criterion $\alpha^{\frac{p-1}{2}}\equiv \left(\frac{\alpha}{p}\right)\pmod{p}$. See my answer here for two proofs why all quadratic residues mod an odd prime $p$ are exactly $\alpha^2,\alpha^4,\ldots,\alpha^{p-1}$, where $\alpha$ is a primitive root mod $p$. In particular, $\alpha, \alpha^3,\ldots, \alpha^{p-2}$ are not quadratic residues mod $p$, so $\alpha$ is not a quadratic residue mod $p$, so $\left(\frac{\alpha}{p}\right)=-1$, so $\alpha^{\frac{p-1}{2}}\equiv -1\pmod{p}$.

Answer 3

$\alpha$ being a primitive element of $\mathbb{Z^{^*}_{_p}}$ we have, $o(\alpha)=p-1$ in $\mathbb{Z^{^*}_{_p}}$. Now $p$ is of the form $p=2^n+1\implies p-1=2^n$ so $(p-1)/2=2^{n-1}$. We know that if $x^2\equiv1(\mod p)$ for some prime $p$ then either $x\equiv1(\mod p)$ or $x\equiv-1(\mod p)$. But if $\alpha^{(p-1)/2}\equiv1(\mod p)$ then it will contradict the fact that $o(\alpha)=p-1$ in $\mathbb{Z^{^*}_{_p}}$. So $\alpha^{(p-1)/2}\equiv-1(\mod p)$ must be true.