Using the properties of Legendre symbols, I need to show $\left(\frac{-1}{n}\right) = (-1)^{\frac{n-1}{2}}$

Here is what I have so far

$\left(\frac{-1}{n}\right) = \left(\frac{-1}{p_1}\right)\left(\frac{-1}{p_2}\right) \cdots \left(\frac{-1}{p_k}\right)$ Where $p_1p_2\cdots p_k$ is the prime factorization of $n$. via the definition of Jacobi Symbols.

From the properties of Legendre symbols this is

$(-1)^{\frac{p_1 - 1}{2}}(-1)^{\frac{p_2 -1 }{2}} \cdots (-1)^{\frac{p_k-2}{2}} = (-1)^{\frac{p_1-1}{2}+\frac{p_2-1}{2}+\cdots + \frac{p_k-1}{2}}$

If I can show that $\frac{n-1}{2} \equiv \frac{p_1-1}{2}+\frac{p_2-1}{2}+\cdots + \frac{p_k-1}{2} \pmod{2}$. Then I would be there (I think).

I've been struggling with this for about an hour, and then decided to search. I found this question. However I don't understand the Lemma the answerer used in his proof.

Lemma 1

Let $a, b$ be odd integers.

Then $(ab - 1)/2 \equiv (a - 1)/2 + (b - 1)/2$ (mod $2$).


Since $a - 1$ and $b - 1$ are even,

$(a - 1)(b - 1) \equiv 0$ (mod $4$).

Hence $ab - a - b + 1 \equiv 0$ (mod $4$).

Hence $ab - 1 \equiv (a - 1) + (b - 1)$ (mod $4$).

Hence $(ab - 1)/2 \equiv (a - 1)/2 + (b - 1)/2$ (mod $2$).

Specifically how we go from this (which I understand)

Hence $ab - a - b + 1 \equiv 0$ (mod $4$).

To this

Hence $ab - 1 \equiv (a - 1) + (b - 1)$ (mod $4$).

Which I'm sure really obvious, but I just cant see it :(

If I understood that, can I then just use it to finish off the proof by stating that

$\frac{p_1-1}{2}+\frac{p_2-1}{2}+\cdots + \frac{p_k-1}{2} \equiv \frac{n-1}{2}\pmod{2}$ via lemma above, and so it follows that

$\left(\frac{-1}{n}\right) = (-1)^{\frac{n-1}{2}}$

Thanks for any help or insight

  • $\begingroup$ In $\left(\frac{-1}{n}\right) = (-1)^{\frac{n-1}{2}}$ the LHS is completely multipliccative by definition. Show the RHS is completely multiplicative too, thus it suffices to look at $n$ prime. $\endgroup$ – reuns Oct 23 '17 at 3:12
  • $\begingroup$ @reuns I'm not sure I follow....show $(n-1) = ( (p_1p_2\cdots p_k) -1)$? $\endgroup$ – XRBtoTheMOON Oct 23 '17 at 3:38
  • $\begingroup$ For $n$ odd let $f(n) = \left(\frac{-1}{n}\right)$ and $g(n) = (-1)^{\frac{n-1}{2}}$, for $n$ even set $f(n) = g(n)=0$. By definition $f(n) = \prod_{p^k \| n} f(p)^k$. And it is clear that $g(mn) = g(m)g(n)$ so $g(n) = \prod_{p^k \| n} g(p)^k$. Thus it suffices to check that $f(p) = g(p)$. $\endgroup$ – reuns Oct 23 '17 at 4:06

You are making hard work of this. The point is to prove that $$\left(\frac{-1}n\right)=\chi(n)\tag1$$ where $$\chi(n)=\begin{cases}1&\text{if }n\equiv1\pmod 4,\\ -1&\text{if }n\equiv-1\pmod 4\end{cases}$$ for odd $n$. Now $\chi(mn)=\chi(m)\chi(n)$ and also $\left(\frac{-1}{mn}\right)=\left(\frac{-1}m\right) \left(\frac{-1}n\right)$. So if ($1$) holds for $m$ and $n$ it holds for $mn$, and it holds for all odd primes....

  • $\begingroup$ that makes sense, and I think I understand it, but if I don't explicitly tie $\frac{n-1}{2}$ into it, I wont get any credit. or is that obvious in there and I just dont see that either, lol. Thanks for your help $\endgroup$ – XRBtoTheMOON Oct 23 '17 at 3:25
  • $\begingroup$ $\chi(n)$ is $(-1)^{(n-1)/2}$ $\endgroup$ – Lord Shark the Unknown Oct 23 '17 at 5:59

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.