[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*}
[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]
[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]
