# Thread: Sum of Legendre Symbols

1. ## Sum of Legendre Symbols

Let $f(x) = a*x^2 + b*x + c$ and $d = b^2 - 4*a*c$
Let p be prime, such that p doesn't divide a.
Show if p doesn't divide d then

$\sum_{x=1}^{p}\ (\frac{f(x)}{p}) = (-1)*(\frac{a}{p})$

We're given that the sum as $\sum_{x=1}^{p}\\x^k\\\equiv$ 0 (mod p) if p-1 doesn't divide k and is = p-1 if p-1 divides k.

My prof also gave the hint that using euler's criterion will let us use the identity given, but i don't see it

2. Note that: $4a\cdot{f(x)}=(2a\cdot x +b)^2-(b^2-4ac)$

So we can write: $\left( {\tfrac{a}
{p}} \right)_L \cdot \left( {\tfrac{{f\left( x \right)}}
{p}} \right)_L = \left( {\tfrac{{4af\left( x \right)}}
{p}} \right)_L = \left( {\tfrac{{\left( {2ax + b} \right)^2 - \left( {b^2 - 4ac} \right)}}
{p}} \right)_{_L }$

That is: $
\left( {\tfrac{{f\left( x \right)}}
{p}} \right)_L = \left( {\tfrac{a}
{p}} \right)_L \cdot \left( {\tfrac{{\left( {2ax + b} \right)^2 - \left( {b^2 - 4ac} \right)}}
{p}} \right)_{_L }
$
and therefore: $\sum_{x=1}^{p}{
\left( {\tfrac{{f\left( x \right)}}
{p}} \right)_L }= \left( {\tfrac{a}
{p}} \right)_L \cdot \sum_{x=1}^{p}{\left( {\tfrac{{\left( {2ax + b} \right)^2 - \left( {b^2 - 4ac} \right)}}
{p}} \right)_{_L } }
$
$(*)$

By Euler's Criterion: $
\sum\limits_{x = 1}^p {\left( {\tfrac{{\left( {2ax + b} \right)^2 - \left( {b^2 - 4ac} \right)}}
{p}} \right)_{_L } } \equiv \sum\limits_{x = 1}^p {\left[ {\left( {2ax + b} \right)^2 - \left( {b^2 - 4ac} \right)} \right]^{\tfrac{{p - 1}}
{2}} } (\bmod. p)
$

Apply the Binomial Theorem to each term: $
\sum\limits_{x = 1}^p {\left[ {\left( {2ax + b} \right)^2 - \left( {b^2 - 4ac} \right)} \right]^{\tfrac{{p - 1}}
{2}} } = \sum\limits_{x = 1}^p {\sum\limits_{k = 0}^{\tfrac{{p - 1}}
{2}} {\binom{\tfrac{p-1}{2}}{k}\left( {2ax + b} \right)^{2k} \cdot \left( { - d} \right)^{\tfrac{{p - 1}}
{2} - k} } }
$
$=
\sum\limits_{k = 0}^{\tfrac{{p - 1}}
{2}} {\binom{\tfrac{p-1}{2}}{k}\left( {\sum\limits_{x = 1}^p {\left( {2ax + b} \right)^{2k} } } \right) \cdot \left( { - d} \right)^{\tfrac{{p - 1}}
{2} - k} }$

Apply The binomial Theorem to: $
\sum\limits_{x = 1}^p {\left( {2ax + b} \right)^{2k} }
$
getting, by the sum you gave down there: $
\sum\limits_{x = 1}^p {\left( {2ax + b} \right)^{2k} } \equiv _p \left\{ \begin{gathered}
0{\text{ if }}k < \tfrac{{p - 1}}
{2} \hfill \\
\sum\limits_{x = 1}^p {\left( {2ax} \right)^{p - 1} } \equiv - 1{\text{ if }}k = \tfrac{{p - 1}}
{2} \hfill \\
\end{gathered} \right.
$

Thus: $
\sum\limits_{x = 1}^p {\left[ {\left( {2ax + b} \right)^2 - \left( {b^2 - 4ac} \right)} \right]^{\tfrac{{p - 1}}
{2}} } \equiv{-1} (\bmod.p)
$
and by $(*)$ we get the result