Legendre symbol

From Wikipedia, the free encyclopedia

The Legendre symbol is a number theory concept. It is named after the French mathematician Adrien-Marie Legendre and is used in connection with factorization and quadratic residues.

[edit] Definition

The Legendre symbol is defined as follows:

If p is an odd prime number and a is an integer, then the Legendre symbol

\left(\frac{a}{p}\right)

is:

  • 0 if p divides a; otherwise,
  • 1 if a is a square modulo p — that is to say there exists an integer k such that k2 ≡ a (mod p), or in other words a is a quadratic residue modulo p;
  • −1 if a is not a square modulo p, or in other words a is not a quadratic residue modulo p.

[edit] Properties of the Legendre symbol

There are a number of useful properties of the Legendre symbol which can be used to speed up calculations. They include:

  1. \left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) (it is a completely multiplicative function in its top argument)
  2. If a ≡ b (mod p), then \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)
  3. \left(\frac{1}{p}\right) = 1
  4. \left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}=\begin{cases}1\mbox{ if }p \equiv 1\pmod{4} \\-1\mbox{ if }p \equiv 3\pmod{4} \end{cases}
  5. \left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}=\begin{cases}1\mbox{ if }p \equiv 1\mbox{ or }7 \pmod{8} \\-1\mbox{ if }p \equiv 3\mbox{ or }5 \pmod{8} \end{cases}
  6. \left(\frac{3}{p}\right)=\begin{cases}1\mbox{ if }p \equiv 1\mbox{ or }11 \pmod{12} \\-1\mbox{ if }p \equiv 5\mbox{ or }7 \pmod{12} \end{cases}
  7. \left(\frac{5}{p}\right)=\begin{cases}1\mbox{ if }p \equiv 1\mbox{ or }4 \pmod5 \\-1\mbox{ if }p \equiv 2\mbox{ or }3 \pmod5 \end{cases}
  8. If q is an odd prime then \left(\frac{q}{p}\right) = \left(\frac{p}{q}\right)(-1)^{ ((p-1)/2) ((q-1)/2) }

The last property is known as the law of quadratic reciprocity. The properties 4 and 5 are traditionally known as the supplements to quadratic reciprocity. They may both be proved from Gauss's lemma.

The Legendre symbol is related to Euler's criterion and Euler proved that

\left(\frac{a}{p}\right) \equiv a^{(p-1)/2}\pmod p

Additionally, the Legendre symbol is a Dirichlet character.

[edit] Related function

The Jacobi symbol is a generalization of the Legendre symbol that allows composite bottom numbers. This generalization provides an efficient way to compute Legendre symbols.

Another generalization is the Kronecker symbol.

Retrieved from "http://en.wikipedia.org../../../l/e/g/Legendre_symbol.html"