Legendre symbol, second supplementary law

Question

$$\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$$

Answer 1

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}$.

Answer 2

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.

Answer 3

Here is a proof from Ireland-Rosen Ch-6 (The key idea is to work in $ \overline{\mathbb{Z}} $, modulo $ p \overline{\mathbb{Z}} $) :

Let $ p $ be an odd prime. We have $ \left( \frac{2}{p} \right) \equiv 2^{\frac{p-1}{2}} (\text{mod } p\mathbb{Z} ) $. Notice we can write $ 2^{\frac{1}{2}} $ as $ 2^{\frac{1}{2}} = 2 \cos \left(\frac{2 \pi}{8} \right) = \zeta + \frac{1}{\zeta} $ (where $ \zeta := e^{\frac{i 2 \pi}{8}} $), and now both $ \zeta, \zeta + \frac{1}{\zeta} \in \overline{\mathbb{Z}} $ (because $\zeta$ satisfies $ X^4 + 1 = 0$, and $ \zeta + \frac{1}{\zeta} $ satisfies $ X^2 - 2 = 0 $).

So we have $ \left( \frac{2}{p} \right) \equiv \left( \zeta + \frac{1}{\zeta} \right)^{p-1} (\text{mod } p\overline{\mathbb{Z}}), $ in $ \overline{\mathbb{Z}} $. Now writing $ \eta := \zeta + \frac{1}{\zeta} ( = 2^{\frac{1}{2}} ) $, we get $ \left( \frac{2}{p} \right) \eta \equiv \eta^p \equiv \zeta^p + \zeta^{-p} \, ( \text{mod } p\overline{\mathbb{Z}})$.

But notice $ \zeta^p + \zeta^{-p} $ is determined by the value of ($ p $ mod $ 8 $), and it is in fact $ 2^{\frac{1}{2}} $ when $ p \equiv \pm 1 \, (\text{mod } 8) $ and $ -2^{\frac{1}{2}} $ when $ p \equiv \pm 3 \, ( \text{mod } 8 ) $. We can encapsulate this casework by writing $ \zeta^p + \zeta^{-p} = (-1)^{\frac{p^2-1}{8}} 2^{\frac{1}{2}} $ (because $ p $ can only be of the form $ 8k \pm 1 $ or $ 8k \pm 3 $, and $ (-1)^{\frac{p^2-1}{8}} $ is $ (-1) $ if former and $ 1 $ if latter).

So finally $ \left( \frac{2}{p} \right) \eta \equiv (-1)^{\frac{p^2-1}{8}} \eta \, (\text{mod }p\overline{\mathbb{Z}}) $. Notice multiplying by $ \eta $ makes both sides integers. Therefore $ \dfrac{\left( \frac{2}{p} \right) 2 - (-1)^{\frac{p^2 - 1}{8}} 2 }{p} \in \overline{\mathbb{Z}} \cap \mathbb{Q} = \mathbb{Z} $, giving us $ \left( \frac{2}{p} \right) = (-1)^{\frac{p^2 -1}{8}} $.