A property of the Legendre symbol

Question

There is a property of Legendre symbol:

$$ \sum_{0\leq k \leq p-1} \left(\frac{k^2-d}{p}\right)=\sum_{0\leq j \leq p-1}\left(1+\left(\frac{j}{p}\right)\right)\left(\frac{j-d}{p}\right) $$

with $\gcd(d,p)=1$. I already know that $$ \sum_{0\leq k \leq p-1} \left(1+\left(\frac{k^2-d}{p}\right)\right) $$

is the number of solutions for $x^2 \equiv k^2-d \pmod{p}$. I am wondering how to go from here to prove this property of Legendre symbol?

Answer 1

More generally, if $g$ is a function on $\mathbb Z_p$, then:

$$\sum_{k\in \mathbb Z_p} g(k^2)=\sum_{j\in \mathbb Z_p}(1+\left(\frac{j}{p}\right))g(j)$$

That's because $1+\left(\frac{j}{p}\right)$ is the number of square roots of $j$, modulo $p$.

So you can change the RHS to be:

$$\sum_{j\in \mathbb Z_p} g(j) \hspace{0.2em}\sum_{n\in \mathbb Z_p}_{n^2= j}1$$

Switching sums, you get:

$$\sum_{n \in \mathbb Z_p}\hspace{0.2em}\sum_{j\in \mathbb Z_p}_{j= n^2}g(j)$$

But the inner sum is just one term, so you get:

$$\sum_{0\leq n \leq p-1}g(n^2)$$

In your case, $g(n) = \left(\frac{n-d}{p}\right)$.

Answer 2

An alternative proof that is much the same as Thomas Andrews':

Recall that the Legendre symbol is a multiplicative quadratic character on $\mathbb{F}_p$. In particular, by orthogonality, we have

$$ \sum_{x \in \mathbb{F}_p} \left( \frac{x}{p} \right) = 0. $$

This statement follows easily from the fact that there are just as many residues as nonresidues in $\mathbb{F}_p$ when $p$ is odd, but I think it is important to understand the more general structure. We wish to find a value for

$$ \sum_{k \in \mathbb{F}_p}\left(\frac{k^2 - d}{p} \right). $$

We have

$$ \sum_{k \in \mathbb{F}_p} \left(\frac{k^2 - d}{p} \right) = \sum_{y \in \mathbb{F}_p} \left(\frac{y}{p}\right)N(y), $$

where we made the Change of Variables $y = k^2 - d$, and

$$ N(y) = \# \{y \in \mathbb{F}_p : y = k^2 - d\}. $$

Note that $y = k^2 - d$ has a solution if and only if $y + d$ is a square. Hence,

$$ N(y) = 1 + \left( \frac{y+d}{p} \right). $$

Then, we see that

$$\begin{align} \sum_{y \in \mathbb{F}_p} \left( \frac{k^2 - d}{p} \right) &= \sum_{y \in \mathbb{F}_p} \left( 1 + \left( \frac{y+d}{p} \right) \right) \left(\frac{y}{p} \right). \end{align}$$

Finally, the change of variables $j \to y - d$ yields what we want:

$$ \sum_{j \in \mathbb{F}_p} \left(1 + \left( \frac{j}{p} \right) \right) \left( \frac{j - d}{p} \right). $$

The advantage to this method is that it required basically no ingenuity. Applying the change of variables made it clear the quantity we wanted to evaluate (which was $N(y)$ using my notation), and this was straight-forward using your own observations.