# Legendre symbol, second supplementary law

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

• The exponent is not equal to $n$ in Gauss Lemma. But obviously it has the same parity.
Aug 7 '12 at 16:58
• @Pantelis Damianou, but from where they got this (p^2-1)/8 ?
– Yola
Aug 7 '12 at 17:02

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

• Moschops: If you happen to catch this, the step you'd asked me about, $(-1)^{1 + \dots + s} = (-1)^{s(s+1)/2}$ is an application of the classical sum of the first $n$ integers. $\sum_1^n i = n(n+1)/2$, which can be proved with induction or combinatorially (both have been asked on this site a few times). Aug 22 '12 at 18:39

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.

• Proof would be great, you could give me link, to not type it, or send me on email if its not prohibited here.
– Yola
Aug 7 '12 at 17:08
• +1, thank you, i`ll accept mixedmath, because of simplicity.
– Yola
Aug 8 '12 at 7:28

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