# Thread: Sum of Legendre Symbols

1. ## Sum of Legendre Symbols

Let $\displaystyle f(x) = a*x^2 + b*x + c$ and $\displaystyle 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

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

We're given that the sum as $\displaystyle \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: $\displaystyle 4a\cdot{f(x)}=(2a\cdot x +b)^2-(b^2-4ac)$

So we can write: $\displaystyle \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: $\displaystyle \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: $\displaystyle \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 } }$ $\displaystyle (*)$

By Euler's Criterion: $\displaystyle \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: $\displaystyle \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} } }$ $\displaystyle = \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: $\displaystyle \sum\limits_{x = 1}^p {\left( {2ax + b} \right)^{2k} }$ getting, by the sum you gave down there: $\displaystyle \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: $\displaystyle \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 $\displaystyle (*)$ we get the result