## 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

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.