prove that $\sum_{j=1}^{p-1} (\frac jp) = 0$ and that $\sum_{k=1}^{p-2} (\frac{k(k-1)}{p}) = -1$ where $(\frac ap)$ is the Legendre symbol.

you should be able to use the latter relation to show that there are always either two consecutive quadratic residues or two consecutive nonresidues mod p

  • $\begingroup$ The answer here might prove useful here. $\endgroup$ – Old John Dec 18 '13 at 22:02
  • $\begingroup$ I have editied your question, but in the second sum you have $k=1$ ... should that be $k-1$ or $k+1$ maybe? $\endgroup$ – Old John Dec 18 '13 at 22:08
  • $\begingroup$ @OldJohn: OP can decide, but we need $k+1$. $\endgroup$ – André Nicolas Dec 18 '13 at 22:40
  • $\begingroup$ @AndréNicolas exactly - I was trying to get OP to make a decision, but the last editor seems to have made the decision for them. $\endgroup$ – Old John Dec 18 '13 at 22:42
  • $\begingroup$ it should have been k+1. thank you for all the help! its much appreciated $\endgroup$ – david Dec 18 '13 at 23:09

The first result is an immediate consequence of the fact that if $p$ is an odd prime, it has exactly as many QR as NR in the interval $[1,p-1]$.

For the second, I take it we want to find $\sum_1^{p-2}\left(\frac{k(k+1)}{p}\right)$.

Let $k^\ast$ be (the least positive residue of) the inverse of $k$ modulo $p$. Then $$\left(\frac{k(k+1)}{p}\right)=\left(\frac{k(k+kk\ast)}{p}\right)=\left(\frac{k^2(1+k^\ast)}{p}\right)=\left(\frac{1+k^\ast}{p}\right).$$

As $k$ travels through the numbers $1$ to $p-2$, the numbers $1+k^\ast$ travel through the integers from $2$ to $p-1$. So our sum is the sum of all the Legendre symbols $\left(\frac{z}{p}\right)$ except $\left(\frac{1}{p}\right)$. This Legendre symbol is $1$. By the first result, the sum of all the Legendre symbols is $0$. This yields the second result.

Remark: We leave to you to show that from the second result that any prime $\gt 3$ has $2$ consecutive QR or two consecutive NR. (There are simpler ways to show that.)


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.