Legendre symbol

The Legendre symbol is used by mathematicians in the theory of numbers, particularly in the fields of factorization and quadratic residues. It is named after the French mathematician Adrien-Marie Legendre.

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:

• 1 if a is a square modulo p (that is to say there exists an integer x such that x² = a mod p)
• -1 if a is not a square modulo p.

Furthermore, if a is divisible by p we define (a/p) = 0.

Euler proved that

<math>

\frac{a}{p} = a^{\frac{p-1}{2}}\mod p </math>

if p is an odd prime. (We have (a/2) = 1 for all odd numbers a and (a/2) = 0 for all even numbers a.)

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.