Euler's criterion for finding if a number is quadratic residue... how does it work?

[MathNugget]

Suppose p is an odd prime number, and $a \in \mathbb{Z}_p$, $a \neq 0$.

I am interested in the implication:
if $a^{\frac{p-1}{2}}\equiv 1$ (mod p), then a is quadratic residue.

It's pretty clear that $a^{\frac{p-1}{2}+1}\equiv a$ (mod p), and if $\frac{p-1}{2}+1=\frac{p+1}{2}$ is even, $x=a^{\frac{p+1}{4}}$.

What happens if $p \equiv 1$ (mod 4)? I get that there is x so that $X^2\equiv 1$ (mod p), which doesn't really help much.

 

[MathNugget]

I realized that $a^{\frac{p-1}{2}}a^p=a^{\frac{3p-1}{2}}\equiv a$, and $\frac{3p-1}{4} \in \mathbb{Z}$, so maybe
$(a^{\frac{3p-1}{4}})^2 \equiv a$ (mod p), which would solve the problem.

There is also the thing that $\frac{3p-1}{4} < p$, which is interesting since...how can this be? I thought it is impossible to have $$a^i\equiv a^j \equiv a$$ (mod p), with 1<i < j< p.

 

[MathNugget]

late realization: the last part was wrong:

I thought it is impossible to have $$a^i\equiv a^j \equiv a$$ (mod p), with 1<i < j< p.

I have that $6^2\equiv -1$ mod 37, so $6^5\equiv 6^{9} \equiv ... \equiv 6^{37}\equiv 6$ mod 37...

I also realized that I was mistaken earlier, if $p \equiv 1$ (mod 4), $4 \nmid 3p-1$... so I still don't know how to prove:

$\forall a \in \mathbb{Z}_p$, $a\neq 0$, $p \equiv 1$ mod 4, there is an x so that $x^2\equiv a$ (mod p)...