If p is a prime number and a is an integer relatively prime to p, then we define the Legendre symbol (a/p) to be:
Euler proved that
Thus we can see that the Legendre symbol is completely multiplicative, i.e. (ab/p) = (a/p)(b/p), and a Dirichlet character.
The Legendre symbol can be used to compactly formulate the law of quadratic reciprocity. This law relates (p/q) and (q/p) and, together with the multiplicity, can be used to quickly compute Legendre symbols.
(a/b) where b is composite is defined as the product of (a/p) over all prime factors p of b, including repetitions. This is called the Jacobi symbol. The Jacobi symbol can be 1 without a being a quadratic residue of b.