Krdytkyu

When $p$ is a prime, we know that Legendre symbol of $a$ is $$left(frac{a}{p}right) = a^{({p-1})/{2}}$$
Suppose $a$ is a square, then $a = x^2$ for some $x$. Therefore, $a^{frac{p-1}{2}} = x^{p-1} = 1$ by Fermat's little theorem. But if $a$ is not a square, then how to prove that $a^{frac{p-1}{2}} = -1$?

First of all, there are two commonly used definitions of the Legendre symbol $left( frac ap right)$. One is simply that $$left( frac ap right) equiv a^tfrac{p-1}{2} pmod p$$ for any integer $a$ and any odd prime $p$. Of course, this congruence only defines $left( frac ap right)$ modulo $p$, but by convention (and for convenience) we normally choose the solution closest to zero.

The other definition is that $$
left( frac ap right) = begin{cases}
phantom+ 0 & text{if } a equiv 0 pmod p, \
phantom+ 1 & text{if } a notequiv 0 pmod p text{ and } a equiv b^2 pmod p text{ for some } b, text{ and} \
-1 & text{otherwise.}
end{cases}$$

By Euler's criterion, these two definitions are equivalent, which I assume is what you're trying to prove. The Wikipedia page I just linked to already gives a pretty good description of how to prove this, so let me just essentially recap it here:

The case when $a equiv 0 pmod p$ is trivial, since it's an elementary result of modular arithmetic that $a^n equiv 0^n equiv 0 pmod p$ for any positive exponent $n$ in this case.

By Fermat's little theorem, we know that $a^p equiv a pmod p$. If $a notequiv 0 pmod p$, then it directly follows that $a^{p-1} equiv 1 pmod p$. Rewriting this as $a^{p-1}-1 equiv 0 pmod p$ and factoring (using the fact that $p$ is odd by definition, and thus $p-1$ is even) gives $$left( a^frac{p-1}{2} + 1 right)left( a^frac{p-1}{2} - 1 right) equiv 0 pmod p.$$ Since the integers modulo a prime $p$ have no zero divisors, one of the factors on the left hand side must be congruent to zero for this congruence to hold, and thus $a^{(p-1) mathop/ 2} equiv pm1 pmod p$ for all $a notequiv 0 pmod p$. To complete the proof, all we need to do is figure out which case holds for each non-zero $a$.

If $a equiv b^2 pmod p$ for some integer $b$, then $a^{(p-1) mathop/ 2} equiv (b^2)^{(p-1) mathop/ 2} = b^{,p-1} equiv 1 pmod p,$ where the last congruence again follows from Fermat's little theorem. Thus, $a^{(p-1) mathop/ 2} equiv 1 pmod p$ for all quadratic residues $a$ modulo $p$.

Finally, to show that $a^{(p-1) mathop/ 2} equiv -1 pmod p$ for all quadratic non-residues, we can apply Lagrange's theorem to show that:

• 
  $a^{(p-1) mathop/ 2} equiv 1$ has at most $(p-1) mathop/ 2$ solutions modulo $p$, and


• 
  $b^2 equiv a$ can have at most two solutions modulo $p$ for each $a$.

Thus, since there are $p-1$ non-zero integers $b$ modulo $p$, then by the pigeonhole principle there must be at least $(p-1) mathop/ 2$ non-zero integers $a$ modulo $p$ for which $b^2 equiv a pmod p$ has a solution (and which thus are quadratic residues). Combining this with the earlier results above, we can see that there must be exactly $(p-1) mathop/ 2$ non-zero quadratic residues modulo $p$, and that those must be the only solutions to $a^{(p-1) mathop/ 2} equiv 1 pmod p$. Thus, for all other non-zero $a$, we must have $a^{(p-1) mathop/ 2} equiv -1 pmod p$, since we have already proved that those are the only possible options.