0
$\begingroup$

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?

2 Answers 2

3

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)$.

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.