Theorem (Euler's Criterion)
Let  {jatex options:inline}p{/jatex}  be an odd prime and let  {jatex options:inline}a \neq 0 \; (mod \; p){/jatex}  be an integer. Then  {jatex options:inline}a{/jatex}  is a quadratic residue of  {jatex options:inline}p{/jatex}  if and only if  {jatex options:inline}a^{\frac{p-1}{2}} \equiv 1 \; (mod \; p){/jatex}, and is a quadratic non residue of  {jatex options:inline}p{/jatex}  if and only if  {jatex options:inline}a^{\frac{p-1}{2}} \equiv -1 \; (mod \; p){/jatex}.
Proof
Let  {jatex options:inline}a{/jatex}  be a quadratic non residue of  {jatex options:inline}p{/jatex}  and let  {jatex options:inline}1 \le b \le p-1{/jatex}  be an integer. The linear congruence  {jatex options:inline}bx \equiv a \; (mod \; p){/jatex}  has a unique solution  {jatex options:inline}1 \le b' \le p-1{/jatex}.  {jatex options:inline}b \neq b'{/jatex}  otherwise  {jatex options:inline}b^2 \equiv 1 \; (mod \; p){/jatex}  and  {jatex options:inline}a{/jatex}  would be a quadratic residue of  {jatex options:inline}p{/jatex}. It follows that the set  {jatex options:inline}\{ 1, \' 2,..., \; p-1 \}{/jatex}  falls into  {jatex options:inline}\frac{p-1}{2}{/jatex}  disjoint pairs  {jatex options:inline}(b, \; b'){/jatex}  with the property that  {jatex options:inline}bb' \equiv a \; (mod \; p){/jatex}. Multiplying these pairs together gives
{jatex options:inline}(p-1)! \equiv a^{\frac{p-1}{2}} \; (mod \; p){/jatex}.
From Wilson's Theorem,  {jatex options:inline}(p-1)! \equiv 1 \; (mod \; p){/jatex}  so  {jatex options:inline}a^{\frac{p-1}{2}} \equiv -1 \; (mod \; p){/jatex}  for any quadratic non residue  {jatex options:inline}a{/jatex}.
Let  {jatex options:inline}a{/jatex}  be a quadratic residue of  {jatex options:inline}p{/jatex}  so that  {jatex options:inline}x^2 \equiv a \; (mod \; p){/jatex}  has a solution. In fact it will have two solutions. Lagrange's Theorem guarantees at most two solutions, and if  {jatex options:inline}1 n\le c \le p-1{/jatex}  is a solution then so is  {jatex options:inline}1 n\le p-c \le p-1{/jatex}, since  {jatex options:inline}(p-c)^2=p^2-2pc+c^2 \equiv c^2 \; (mod \; p){/jatex}.
If we remove  {jatex options:inline}c, \; p-c{/jatex}  from the set  {jatex options:inline}\{ 1, \; 2,..., \; p-1 \}{/jatex}  then as before the remaining  {jatex options:inline}p-3{/jatex}  integers fall into  {jatex options:inline}\frac{p-3}{2}{/jatex}  disjoint pairs  {jatex options:inline}(b, \; b'){/jatex}  with the property that  {jatex options:inline}bb' \equiv a \; (mod \; p){/jatex}. Then
{jatex options:inline}\begin{aligned} (p-1)! &= 1 \times 2 \times 3 \times ... c \times ... \times (p-c) \times ... \times (p-1) \\ & \equiv a^{\frac{p-3}{2}} c(p-c) \; (mod \; p) \\ & \equiv a^{\frac{p-3}{2}} (-c^2) \; (mod \; p) \\ & \equiv a^{\frac{p-3}{2}} (-a) \; (mod \; p) \\ & \equiv -a^{\frac{p-1}{2}} \; (mod \; p) \end{aligned}{/jatex}
Using Wilson's Theorem as before,
{jatex options:inline}-1 \equiv -a^{\frac{p-1}{2}} \; (mod \; p) \rightarrow 1 \equiv a^{\frac{p-1}{2}} \; (mod \; p){/jatex}
for any quadratic residue  {jatex options:inline}a{/jatex}.
Suppose now that  {jatex options:inline}a^{\frac{p-1}{2}} \equiv 1 \; (mod \; p) \; 1 \le a \le (p-1){/jatex}.  {jatex options:inline}a{/jatex}  is either a quadratic residue or a quadratic non residue of  {jatex options:inline}p{/jatex}. If it is a quadratic non residue then  {jatex options:inline}a^{\frac{p-1}{2}} \equiv 1 \; (mod \; p){/jatex}  and this would imply  {jatex options:inline}1 \equiv -1 \; (mod \; p){/jatex}  which is a contradiction, so if  {jatex options:inline}a^{\frac{p-1}{2}} \equiv 1 \; (mod \; p) {/jatex}  then  {jatex options:inline}a{/jatex}  is a quadratic residue.