The Legendre Symbol

Letbe an odd prime andThe Legendre symbolis defined as

For example,and

The Legendre symbol has the following properties forwhereis an odd prime.

1. Ifthen

2. 

3. 

4. 

5. 

The Legendre symbol can be used to decide if some equationshave solutions. If the equation is quadratic for example,then the existence of solutions reduces to whetheris a quadratic residue of

For the equationthe discriminant is

sinceby 5 above.

The Legendre symbol my be used to find all the quadratic residues (mod p). Ifthen of course1, 4, 9, 16, 25, 36 are quadratic residues.

so -1 is a quadratic residue from 5 above.

so 33 is a quadratic residue.

Similarly,andare quadratic residues.

Alsoandso 3 and 7 are quadratic residues. Using these andthen give

andso 34 and 30 are quadratic residues.

andso 11 and 27 are quadratic residues and so areand