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