Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
$$\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$$ how did they get the exponent. May be from Gauss lemma, but how.
Suppose we have a = 2 and p = 11. Then n = 3 (6,8,10), but not $$15 = (11^2-1)/8$$
n is a way to compute Legendre symbols from Gauss lemma: $$\left(\frac{a}{p}\right) = (-1)^n$$
I don't know how your source arrived at the exponent, but I'll tell you one of my favorite elementary ways of getting there. added ex post facto: this is probably the elementary way that Andre alluded to
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 correct resulting sign.
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}$.
One can indeed use Gauss's Lemma, though there is a more elementary approach playing with factorials and using Euler's Criterion.
The $(p^2-1)/8$ is excessively mysterious-looking. The "real" theorem is that $2$ is a quadratic residue of $p$ if $p\equiv \pm 1\pmod{8}$, and is a non-residue if $p\equiv \pm 3\pmod{8}$.
It is not hard to verify that if $p\equiv \pm 1\pmod{8}$, then $(p^2-1)/8$ is even, and that if $p\equiv \pm 3\pmod{8}$ then $(p^2-1)/8$ is odd. So taking $-1$ to the power $(p^2-1)/8$ gives the right answer for the Legendre symbol $(2/p)$.
Detail: If $p=8k\pm 1$, then $p^2-1=64k^2\pm 16k$, so $(p^2-1)/8=8k^2\pm 2k$, even. If $p=8k\pm 3$, then $p^2-1=64k^2\pm 48k+8$, so $(p^2-1)/8=8k^2\pm 6k+1$, odd.
Proof from Gauss's Lemma: If $1\le j\le (p-1)/2$, then $2\le 2j\le p-1$. Let $N$ be the number of integers in the set $A=\{2,4,\dots,p-1\}$ that are larger than $p/2$. Then by Gauss's Lemma, $(2/p)=(-1)^N$. Now $2j \lt p/2$ iff $j \lt p/4$.
(i) If $p=8k+1$, then $j\lt p/4$ is equivalent to $j \lt 2k+\frac{1}{4}$. There are $2k$ integers satisfying this last inequality. Since $A$ contains $(p-1)/2=4k$ elements, it follows that $N=4k-2k=2k$. So $N$ is even, and therefore $(2/p)=1$.
The other three cases use the same sort of reasoning. If (ii) $p=8k+3$; (iii)$p=8k+5$; or (iv) $p=8k+7$, then $N$ is respectively (ii) $(4k+1)-2k=2k+1$; (iii) $(4k+2)-(2k+1)=2k+1$; or (iv) $(4k+3)-(2k+1)=2k+2$. So in our remaining $3$ cases, $N$ is even only in the case $8k+7$. The rest follows by Gauss's Lemma.
