Legendre symbol

DEFINITION 6.1   Let $p$ be an odd prime. Let $a$ be an integer which is not divisible by $p$ . Then we define the Legendre symbol $\left(\frac{a}{p}\right)$ by the following formula.

$${\left(\frac{a}{p}\right)}= \begin{cases}1 & \text{if }(X^2... ...ucible over }\mathbb{F}_p\\ -1 & \text{otherwise} \end{cases}$$

We further define

$${\left(\frac{a}{p}\right)}= 0$$$$\text { if } a \in p\mathbb{Z}.$$

LEMMA 6.2   Let $p$ be an odd prime. Then:

1. ${\left(\frac{a}{p}\right)}= a^{(p-1)/2} \mod p$
2. ${\left(\frac{ab}{p}\right)}= {\left(\frac{a}{p}\right)} {\left(\frac{b}{p}\right)}$

We note in particular that ${\left(\frac{-1}{p}\right)}=(-1)^{(p-1)/2}$ .

DEFINITION 6.3   Let $p,\ell$ be distinct odd primes. Let $\lambda$ be a primitive $\ell$ -th root of unity in an extension field of ${\mathbb{F}}_p$ . Then for any integer $a$ , we define a Gauss sum $\tau_a$ as follows.

$$\tau_a=\sum_{t=1}^{\ell-1}{\left(\frac{t}{\ell}\right)}\lambda^{at}$$

$\tau_1$ is simply denoted as $\tau$ .

LEMMA 6.4  

1. $\tau_a={\left(\frac{a}{\ell}\right)}\tau$ .
2. $\sum_{a=0}^{l-1} \tau_a \tau_{-a}=\ell(\ell-1)$ .
3. $\tau^2=(-1)^{(\ell-1)/2}\ell$ ( $=\ell^*$ (say)).
4. $\tau^{p-1}=(\ell^*)^{(p-1)/2}$ .
5. $\tau^p=\tau_{p}$ .

THEOREM 6.5   ${\left(\frac{p}{\ell}\right)}={\left(\frac{\ell^*}{p}\right)}$ ( where $\ell^*=(-1)^{(\ell-1)/2}\ell$ ) ${\left(\frac{-1}{\ell}\right)}=(-1)^{(\ell-1)/2}$ ${\left(\frac{2}{\ell}\right)}=(-1)^{(\ell^2-1)/8}$