Legendre symbol

Suppose p is an odd prime and a is any integer. The Legendre symbol (a|p) is defined to be

+1  if a is a quadratic residue (mod p),
−1  if a is a quadratic non-residue (mod p) and,
0  if p divides a

Note: the Legendre symbol is often written vertically: (a|p).

Euler showed that (a|p) ≡ a(p−1)/2 (mod p). Using this we can show the following: Let p and q be odd primes, then

For the prime 2 we have

Far more difficult to prove is the quadratic reciprocity law:

In other words, (p|q) = (q|p), unless pq ≡ 3 (mod 4), in which case (p|q) = −(q|p).

The Legendre symbol is often evaluated by using the Jacobi symbol.

See Also: JacobiSymbol

Printed from the PrimePages <primes.utm.edu> © Chris Caldwell.