I ran into two problems involving sums of Legendre symbols: for $p$ prime and $a,b,k$ integers:

$$\sum_{x=1}^{p} \left(\frac{x(x+k)}{p}\right)$$$$ \sum_{x=1}^{p} \left(\frac{x^2 +ax + b}{p}\right)$$

How can I evaluate these? I have some basic background working with Legendre symbols but not with sums of series.


For the first sum: If $k\equiv 0\mod p$ the first sum is $p-1$. Hence if we assume $k\not \equiv 0 \mod p$ $$\sum_{x \mod p}\bigg(\frac{x^2+kx}{p}\bigg)=\sum_{x \neq 0\mod p}\bigg(\frac{x^2+kx}{p}\bigg)\\ =\sum_{x\neq 0 \mod p}\bigg(\frac{x^2}{p}\bigg)\bigg(\frac{1+kx^{-1}}{p}\bigg)$$ as $\big(\frac{x^2}{p}\big)=1$ for $x\neq 0$ we have $$\sum_{x \mod p}\bigg(\frac{x^2+kx}{p}\bigg)=\sum_{x\neq 0 \mod p}\bigg(\frac{1+kx^{-1}}{p}\bigg)$$ As $\{x :x\neq 0 \mod p\}=\{kx^{-1}: x\neq 0 \mod p\}$ we have
$$ \sum_{x\neq 0 \mod p}\bigg(\frac{1+kx^{-1}}{p}\bigg)=\sum_{x\neq 0 \mod p}\bigg(\frac{1+x}{p}\bigg)\\ =\sum_{x\mod p}\bigg(\frac{x}{p}\bigg)-\bigg(\frac{1}{p}\bigg)\\ =-1.$$ Hence the first sum is $p-1$ if $k\equiv 0 \mod p$ and $-1$ if $k\not \equiv 0 \mod p$. I have an explicit expression for the for the second sum in terms of $(\frac{b-2^{-2}a^2}{p})$ and $(\frac{-1}{p})$ but the proof is too long to write it here.

  • $\begingroup$ Could you clarify the step why $\{x :x\neq 0 \mod p\}=\{kx^{-1}: x\neq 0 \mod p\}$? $\endgroup$ – F. Yan May 13 '17 at 3:38
  • $\begingroup$ The set of non zero residues modulo $p$ is a multiplicative group and if $k,x\neq 0$ then clearly $kx^{-1}\neq 0$. Hence $\{kx^{-1}:x\neq 0 \mod p\}$ is a subset of $\{x:x\neq 0\mod p\}$. Every $y\in \{x:x\neq 0\mod p\}$ belongs to $\{kx^{-1}:x\neq 0 \mod p\}$ as when $x=ky^{-1}$, $kx^{-1}=y$. Hence $\{x:x\neq 0\mod p\}$ is a subset of $\{kx^{-1}:x\neq 0 \mod p\}$ which implies $\{x:x\neq 0\mod p\}=\{kx^{-1}:x\neq 0 \mod p\}.$ $\endgroup$ – Sai Teja May 13 '17 at 4:02

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.