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

[MathNugget]

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

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

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

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

 

[MathNugget]

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

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

 

[MathNugget]

late realization: the last part was wrong:

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

I have that [imath]6^2\equiv -1[/imath] mod 37, so [imath]6^5\equiv 6^{9} \equiv ... \equiv 6^{37}\equiv 6[/imath] mod 37...

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

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