Legendre symbol

From Exampleproblems

The Legendre symbol is used by mathematicians in the area of number theory, particularly in the fields of factorization and quadratic residues. It is named after the French mathematician Adrien-Marie Legendre.

Definition

The Legendre symbol is a special case of the Jacobi symbol. It is defined as follows:

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

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

is:

0 if p divides a
1 if a is a square modulo p — that is to say there exists an integer k such that k² ≡ 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</u>

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:

$\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)
If a ≡ b (mod p), then $\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right)$
$\left(\frac{1}{p}\right) = 1$
$\left(\frac{-1}{p}\right) = (-1)^{\left(\frac{p-1}{2}\right)}$ , i.e. = 1 if p ≡ 1 (mod 4) and = −1 if p ≡ 3 (mod 4)
$\left(\frac{2}{p}\right) = (-1)^{\left(\frac{p^2-1}{8}\right)}$ , i.e. = 1 if p ≡ 1 or 7 (mod 8) and = −1 if p ≡ 3 or 5 (mod 8)
If q is an odd prime then $\left(\frac{q}{p}\right) = \left(\frac{p}{q}\right)(-1)^{\left(\frac{p-1}{2}\right)\left(\frac{q-1}{2}\right)}$

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. The 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^{\left(\frac{p-1}{2}\right)}\pmod p$