Encyclopedia  |   World Factbook  |   World Flags  |   Reference Tables  |   List of Lists     
   Academic Disciplines  |   Historical Timeline  |   Themed Timelines  |   Biographies  |   How-Tos     
Sponsor by The Tattoo Collection
Legendre symbol
Main Page | See live article | Alphabetical index

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:

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

Euler proved that

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 in its first argument, 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.