Prove that if $a^{(p-1)/2}\equiv 1 \pmod{p}$ then $a$ is a quadratic residue modulo $p$

Question

I know how to prove this the other way, but I don't see how the if and only if statement works in this direction. One thought I had was to try to show that the exponent was even as I know that this is the only way for $a$ to be a quadratic residue. I'm not really sure how to go about doing this though.

Answer 1

If $a$ is a quadratic residue, there exists $x$ such that $$x^2\equiv a\pmod p$$

$$a^{(p-1)/2}\equiv x^{p-1}\equiv?\pmod p$$

Alternatively $g$ is a primitive root, $$(g^k)^{(p-1)}\equiv1\pmod p$$ will hold true iff $p-1$ divides $k(p-1)/2\iff2|k$

If $k=2m$ $$g^{2m}\equiv(g^m)^2\pmod p$$

Answer 2

The homomorphism $\phi: (\Bbb Z/p \Bbb Z)^* \to (\Bbb Z/ p \Bbb Z)^*$ defined by $\phi(x) = x^2$ has kernel $\{1, -1 \}$, so $|\operatorname{image}(\phi)|= \frac{p-1}{2}.$ Since $(\Bbb Z / p \Bbb Z)^*$ has $\frac{p-1}{2}$ elements satisfying $x^{\frac{p-1}{2}}=1$, $a$ must be in the image of $\phi$.