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

  • $\begingroup$ The exponent is not equal to $n$ in Gauss Lemma. But obviously it has the same parity. $\endgroup$ – PAD Aug 7 '12 at 16:58
  • $\begingroup$ @Pantelis Damianou, but from where they got this (p^2-1)/8 ? $\endgroup$ – 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}$.

| cite | improve this answer | |
  • 1
    $\begingroup$ 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). $\endgroup$ – davidlowryduda 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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