text: Q:
  
  Sum of Legendre symbol
  
  $$\sum_{y=0}^{p-1} \left(\frac {y^2 + d}{p}\right) = \sum_{y=0}^{p-1} \left(1+\left( \frac {y}{p}\right)\right)\left(\frac {y+d}{p}\right)$$
  What is the reason behind this?
  
  A:
  
  Because $1+\left(\frac yp\right)$ is $2$ when $y$ is a non-zero square and $0$ when $y$ is not a square, and $1$ when $y=0.$ Thus, $1+\left(\frac yp\right)$ is equal to the number of values $z$ in $\{0,1,\dots,p-1\}$ such that $z^2\equiv p\pmod{p}.$ So the right side can be written as $$\sum_{z=0}^{p-1}\left(\frac{z^2+d}{p}\right)$$
  More generally, given a function $f$ with $f(x+p)=f(x)$:
  $$\sum_{y=0}^{p-1} f(y^2)=\sum_{y=0}^{p-1} \left(1+\left(\frac yp\right)\right)f(y)$$
  
  