Is there a short proof of the formula for Legendre symbol $(\frac{2}{p})=(-1)^{(p^2-1)/8}$? Let $p$ > 2 be a prime number. I found in wiki a complex proof for this Legendre symbol: 
$$\left(\frac{2}{p}\right)  =  (-1)^{\frac{(p^{2}-1)}{8}}$$ 
Can anyone give me a short solution please?
 A: Let $s = \frac{p-1}{2}$, and consider the $s$ equations
$$\begin{align}
1&= (-1)(-1)  \\
2&=2(-1)^2  \\
3&= (-3)(-1)^3 \\
4&= 4 (-1)^4 \\
 & \quad\quad \ldots\\
s&= (\pm s)(-1)^s
\end{align}$$
Where the sign is always chosen to have the result be positive.
Now multiply the $s$ equations together. Clearly on the left we have $s!$. On the right, we have a $2,4,6,\dots$ and some negative odd numbers. But note that $2(s) \equiv -1 \mod p$, $2(s-1) \equiv - 3 \mod p$, and so on, so that the negative numbers are the rest of the even numbers mod $p$, but disguised. So the right side contains $s! (2^s)$ (where we intuit this to mean that one two goes to each of the terms of the factorial, to represent the even numbers $\mod p$).
We only have consideration of $(-1)^{1 + 2 + \ldots + s} = (-1)^{s(s+1)/2}$ left.
Putting this all together, we get that $2^s s! \equiv s! (-1)^{s(s+1)/2} \mod p$, or upon cancelling factorials that $2^s \equiv (-1)^{s(s+1)/2}$. And $s(s+1)/2 = (p^2 - 1)/8$, so we really have $2^{(p-1)/2} \equiv (-1)^{(p^2 - 1)/8}$.
