# 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*^{2}=*a*mod*p*) - −1 if
*a*is not a square modulo*p*.

*a*is divisible by

*p*we define (

*a/p*) = 0.

Euler proved that

*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*.