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

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.

• The exponent will only be even if $p \equiv 1 \pmod{4}$, and that doesn't have to happen. You still need to handle the case $p \equiv 3 \pmod{4}$. – Robert Shore Mar 21 at 1:32
• When $\ a^{(p-1)/2}\equiv 1 \pmod{p}\$ the Tonelli-Shanks algorithm enables you to calculate the $\hspace{-0.2em}\pmod{p}\$ square-root of $\ a\$ explicitly. See the Wikipedia article at: en.wikipedia.org/wiki/Tonelli–Shanks_algorithm – lonza leggiera Mar 22 at 2:12

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$$

• yes I know by Fermat's Little Theorem that this then is equal to 1. It is proving the other side of the if and only if statement where I am a little confused – joseph Mar 21 at 2:11
• @josephF, Conversely if $x^2\equiv a,a^{(p-1)/2}\equiv -1,$ $$-1\equiv a^{(p-1)/2}\equiv x^{p-1}\equiv1$$ – lab bhattacharjee Mar 21 at 2:28

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$$.