|
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 x2 = 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
-
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.
|