Quadratic residues
Let and
be integers, with
. We say that
is a quadratic residue modulo
if there is some number
so that
is divisible by
.
Legendre Symbol
Determining whether is a quadratic residue modulo
is easiest if
is a prime. In this case we write
The symbol is called the Legendre symbol.
Quadratic Reciprocity
Let and
be distinct odd primes. Then
. This is known as the Quadratic Reciprocity Theorem.
Jacobi Symbol
Now suppose that , as above, is not composite, and let
. Then we write
. This symbol is called the Jacobi symbol.
(I'm sure someone wants to write out all the fun properties of Legendre symbols. It just happens not to be me right now.)