The Legendre Symbol
Letbe an odd prime and
The Legendre symbol
is defined as
For example,and
The Legendre symbol has the following properties forwhere
is an odd prime.
If
then
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 whether
is a quadratic residue of
For the equationthe discriminant is
since
by 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,and
are quadratic residues.
Alsoand
so 3 and 7 are quadratic residues. Using these and
then give
and
so 34 and 30 are quadratic residues.
and
so 11 and 27 are quadratic residues and so are
and