View source for Legendre symbol

An [[Arithmetic function|arithmetic function]] of the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l0580601.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l0580602.png" />, defined for odd prime numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l0580603.png" /> and integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l0580604.png" /> not divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l0580605.png" />. The Legendre symbol is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l0580606.png" />. The Legendre symbol <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l0580607.png" /> if the [[Congruence|congruence]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l0580608.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l0580609.png" /> is solvable; otherwise, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806010.png" />. The Legendre symbol is sometimes defined for numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806011.png" /> divisible by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806012.png" /> by putting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806013.png" /> in this case. The Legendre symbol has the following properties:

1) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806014.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806015.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806016.png" />;

2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806017.png" />;

3) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806018.png" /> <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806019.png" />;

4) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806020.png" />;

5) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806021.png" />;

6) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806022.png" />;

7) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806023.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806024.png" /> are odd prime numbers, then

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806025.png" /></td> </tr></table>

The last fact, first proved by C.F. Gauss (1796), is called the quadratic reciprocity law. The above properties make it possible to calculate the Legendre symbol easily, without resorting to solving congruences. For example,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806026.png" /></td> </tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806027.png" /></td> </tr></table>

The calculation of the Legendre symbol is facilitated still more by the use of the [[Jacobi symbol|Jacobi symbol]]. For fixed <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806028.png" /> the Legendre symbol is a real character of the multiplicative group of residue classes modulo <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l058/l058060/l05806029.png" /> (cf. [[Character of a group|Character of a group]]).

It was introduced by A.M. Legendre in 1785.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  I.M. Vinogradov,   "Elements of number theory" , Dover, reprint  (1954)  (Translated from Russian)</TD></TR></table>



====Comments====


====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  G.H. Hardy,   E.M. Wright,   "An introduction to the theory of numbers" , Oxford Univ. Press  (1979)</TD></TR></table>