Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
The exponent is not equal to $n$ in Gauss Lemma. But obviously it has the same parity. –  PAD 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

2 Answers 2

up vote 9 down vote accepted

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

share|improve this answer
    
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). –  mixedmath 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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.