[proofplan] Write $\chi:\mathbb{Z}\to\{-1,0,1\}$ for the [Legendre symbol](/page/Legendre%20Symbol) modulo $p$. We first use multiplicativity to combine the product $\chi(a)\chi(a+h)$ into $\chi(a(a+h))$, including the zero terms $a\equiv 0$ and $a\equiv -h \pmod p$. Since multiplication by $h$ permutes the residue classes modulo $p$, the substitution $a\equiv hx\pmod p$ reduces the sum to $\sum_x \chi(x(x+1))$. Finally, we count the same sum by the number of solutions of $y^2\equiv x(x+1)\pmod p$, completing the square to show that exactly $p-1$ pairs occur, so the character sum is $-1$. [/proofplan]

[step:Combine the two Legendre symbols into one quadratic character] Define the quadratic character modulo $p$ by \begin{align*} \chi:\mathbb{Z} &\to \{-1,0,1\} \end{align*} \begin{align*} n &\mapsto \left(\frac{n}{p}\right). \end{align*} We use the elementary [multiplicativity of the Legendre symbol](/theorems/1716): \begin{align*} \chi(uv)=\chi(u)\chi(v) \end{align*} for all $u,v\in\mathbb{Z}$. This identity also covers the cases $p\mid u$ or $p\mid v$, because then both sides are $0$. Therefore \begin{align*} \sum_{a=0}^{p-1}\left(\frac{a}{p}\right)\left(\frac{a+h}{p}\right) = \sum_{a=0}^{p-1}\chi(a(a+h)). \end{align*} In particular, the terms with $a\equiv 0\pmod p$ and $a\equiv -h\pmod p$ contribute $0$, as required by the definition of $\chi$. [/step]

[step:Scale the shift to reduce to $x(x+1)$]Since $p\nmid h$, the residue class $\bar h$ is a unit in $\mathbb{Z}/p\mathbb{Z}$. Hence the map \begin{align*} \mathbb{Z}/p\mathbb{Z} &\to \mathbb{Z}/p\mathbb{Z} \end{align*} \begin{align*} \bar x &\mapsto \bar h\bar x \end{align*} is a bijection. Using the substitution $a\equiv hx\pmod p$, and using [periodicity of the Legendre symbol](/theorems/10090), we obtain \begin{align*} \sum_{a=0}^{p-1}\chi(a(a+h)) = \sum_{x=0}^{p-1}\chi(hx(hx+h)). \end{align*} For each $x\in\mathbb{Z}$, \begin{align*} hx(hx+h)=h^2x(x+1). \end{align*} Since $p\nmid h$, the integer $h^2$ is a nonzero square modulo $p$, so $\chi(h^2)=1$. By multiplicativity, \begin{align*} \chi(h^2x(x+1))=\chi(h^2)\chi(x(x+1))=\chi(x(x+1)). \end{align*} Thus \begin{align*} \sum_{a=0}^{p-1}\left(\frac{a}{p}\right)\left(\frac{a+h}{p}\right) = \sum_{x=0}^{p-1}\chi(x(x+1)). \end{align*}[/step]

[guided]The point of this step is to remove the particular nonzero shift $h$. Because $p\nmid h$, multiplication by $\bar h$ has inverse multiplication by $\bar h^{-1}$ in $\mathbb{Z}/p\mathbb{Z}$. Therefore each residue class $\bar a$ occurs exactly once in the form $\bar a=\bar h\bar x$. After substituting $a\equiv hx\pmod p$, the quadratic factor becomes \begin{align*} a(a+h)\equiv hx(hx+h)\equiv h^2x(x+1)\pmod p. \end{align*} The Legendre symbol depends only on the residue class modulo $p$, so this gives \begin{align*} \chi(a(a+h))=\chi(h^2x(x+1)). \end{align*} Now $h^2$ is a square and is not divisible by $p$, so $\chi(h^2)=1$. Multiplicativity gives \begin{align*} \chi(h^2x(x+1))=\chi(h^2)\chi(x(x+1))=\chi(x(x+1)). \end{align*} Hence the original shifted correlation is the normalized shift-free sum \begin{align*} \sum_{x=0}^{p-1}\chi(x(x+1)). \end{align*}[/guided]

[step:Count points on $y^2=x(x+1)$ to evaluate the reduced sum] For each residue class $\bar x\in\mathbb{Z}/p\mathbb{Z}$, the number of residue classes $\bar y\in\mathbb{Z}/p\mathbb{Z}$ satisfying \begin{align*} \bar y^2=\bar x(\bar x+\bar 1) \end{align*} is $1+\chi(x(x+1))$ by [citetheorem:10088]. Therefore the total number $N$ of pairs $(\bar x,\bar y)\in(\mathbb{Z}/p\mathbb{Z})^2$ satisfying \begin{align*} \bar y^2=\bar x(\bar x+\bar 1) \end{align*} is \begin{align*} N=\sum_{x=0}^{p-1}(1+\chi(x(x+1)))=p+\sum_{x=0}^{p-1}\chi(x(x+1)). \end{align*} We now compute $N$. Since $p$ is odd, the residue class $\bar 2$ is invertible in $\mathbb{Z}/p\mathbb{Z}$. Multiplying the equation by $\bar 4$ gives the equivalent congruence \begin{align*} (2\bar y)^2=(2\bar x+\bar 1)^2-\bar 1. \end{align*} Define \begin{align*} U&:=2\bar y, \end{align*} \begin{align*} V&:=2\bar x+\bar 1. \end{align*} The map \begin{align*} (\mathbb{Z}/p\mathbb{Z})^2 &\to (\mathbb{Z}/p\mathbb{Z})^2 \end{align*} \begin{align*} (\bar x,\bar y) &\mapsto (V,U) \end{align*} is a bijection, because multiplication by $\bar 2$ is invertible and translation by $\bar 1$ is invertible. Thus $N$ is the number of pairs $(V,U)\in(\mathbb{Z}/p\mathbb{Z})^2$ satisfying \begin{align*} V^2-U^2=\bar 1. \end{align*} Factoring gives \begin{align*} (V-U)(V+U)=\bar 1. \end{align*} For every unit $r\in(\mathbb{Z}/p\mathbb{Z})^\times$, there is a unique solution determined by \begin{align*} V-U=r,\qquad V+U=r^{-1}. \end{align*} Since $\bar 2$ is invertible, this uniquely determines \begin{align*} V=\frac{r+r^{-1}}{2},\qquad U=\frac{r^{-1}-r}{2}. \end{align*} Conversely, every solution has $V-U\in(\mathbb{Z}/p\mathbb{Z})^\times$ and is obtained in this way. Hence \begin{align*} N=|(\mathbb{Z}/p\mathbb{Z})^\times|=p-1. \end{align*} Combining this with the earlier expression for $N$ gives \begin{align*} p+\sum_{x=0}^{p-1}\chi(x(x+1))=p-1. \end{align*} Therefore \begin{align*} \sum_{x=0}^{p-1}\chi(x(x+1))=-1. \end{align*} [/step]

[step:Transfer the reduced value back to the shifted sum] From the scaling reduction, \begin{align*} \sum_{a=0}^{p-1}\left(\frac{a}{p}\right)\left(\frac{a+h}{p}\right) = \sum_{x=0}^{p-1}\chi(x(x+1)). \end{align*} The counting computation gives \begin{align*} \sum_{x=0}^{p-1}\chi(x(x+1))=-1. \end{align*} Thus \begin{align*} \sum_{a=0}^{p-1}\left(\frac{a}{p}\right)\left(\frac{a+h}{p}\right)=-1, \end{align*} which is the desired identity. [/step]