LEGENDRE SYMBOL

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.

Contents

Definition

Properties of the Legendre symbol

Related function

Definition

The Legendre symbol is defined as follows:
If ''p'' is an odd prime number and ''a'' is an integer, then the Legendre symbol
:
ight)
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 ''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''.

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(rac{ab}{p}
ight) = left(rac{a}{p}
ight)left(rac{b}{p}
ight)
(it is a completely multiplicative function in its top argument)
#If ''a'' ≡ ''b'' (mod ''p''), then $$
left(rac{a}{p}
ight) = left(rac{b}{p}
ight)

#$$
left(rac{1}{p}
ight) = 1

#$$
left(rac{-1}{p}
ight) = (-1)^{(p-1)/2}=egin{cases}1mbox{ if }p equiv 1pmod{4} \-1mbox{ if }p equiv 3pmod{4} end{cases}
#$$
left(rac{2}{p}
ight) = (-1)^{(p^2-1)/8}=egin{cases}1mbox{ if }p equiv 1mbox{ or }7 pmod{8} \-1mbox{ if }p equiv 3mbox{ or }5 pmod{8} end{cases}
#$$
left(rac{3}{p}
ight)=egin{cases}1mbox{ if }p equiv 1mbox{ or }11 pmod{12} \-1mbox{ if }p equiv 5mbox{ or }7 pmod{12} end{cases}
#For an odd prime ''p'', $$
left(rac{5}{p}
ight)=egin{cases}1mbox{ if }p equiv 1mbox{ or }4 pmod5 \-1mbox{ if }p equiv 2mbox{ or }3 pmod5 end{cases}
#If ''p'' and ''q'' are odd primes then $$
left(rac{q}{p}
ight) = left(rac{p}{q}
ight)(-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(rac{a}{p}
ight) equiv a^{(p-1)/2}pmod p

Additionally, the Legendre symbol is a Dirichlet character.

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 all Legendre symbols.
Another generalization is the Kronecker symbol.