$p$ is an odd prime and $a\in\mathbb{Z}$ with $\gcd (a,p)=1$ implies $\exists x\in\mathbb{Z}:x^2\equiv a\bmod p$ iff $a^\frac{p-1}{2}\equiv 1\mod p$

Let $p$ denote an odd prime and let $a\in\mathbb{Z}$ with $\gcd(a,p)=1$. I want to show that it holds $$\exists x\in\mathbb{Z}:x^2\equiv a\text{ mod }p\;\;\;\Leftrightarrow\;\;\;a^\frac{p-1}{2}\equiv 1\text{ mod }p$$

Proof: Since $p$ is prime and $p\nmid a$, it follows from Fermat's little theorem: $$\left(a^\frac{p-1}{2}-1\right)\left(a^\frac{p-1}{2}+1\right)=a^{p-1}-1\equiv0\text{ mod }p$$ But (again) since $p$ is prime, one of the factors on the left side must be multiples of $p$, i.e. $$a^\frac{p-1}{2}\equiv\pm 1\text{ mod }p$$ Now I would like to prove the equivalence. Let's start with the direction "$\Rightarrow$". How do I need to argue here?

PS: I'm not sure where exactly I need that $p$ is uneven, i.e. $p\ne 2$.

• If $p$ is even then $a^{\frac{p-1}{2}}=a^{\frac{1}{2}}$ which might not be an integer. – Rocket Man Jun 9 '14 at 12:21
• Hint: The multiplicative group modulo $p$ is cyclic of order $p-1$. – Hagen von Eitzen Jun 9 '14 at 12:23

One direction is easy if $x^2\equiv a \pmod p$ then taking both sider to power $\frac{p-1}{2}$ we have
$$x^{p-1}\equiv a^{\frac{p-1}{2}} \pmod p$$
but $$x^{p-1}\equiv 1\pmod p$$ so $$a^{\frac{p-1}{2}} \equiv 1\pmod p$$
The other direction is based on the fact that there is a primitive root modulo $p$, a number $g$ such that $g^{p-1}\equiv 1 \pmod p$ and for no smaller power $n < p-1$ is $g^{n}\equiv 1 \pmod p$. If $a\equiv g^k \pmod p$ then $$a^{\frac{p-1}{2}} \equiv g^{k\frac{p-1}{2}}\pmod p$$
so $$g^{k\frac{p-1}{2}}\equiv 1\pmod p$$ which means that $p-1|k\frac{p-1}{2}$ and this can only happen if $k$ is even, $k=2l$ so let $x=g^l$ and then
$$x^2\equiv a \pmod p$$