Encyclopedia > Legendre symbol

Article Content

Legendre symbol

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

$\frac{a}{p} = a^{\frac{p-1}{2}}\mod p$

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, 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.

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia
 Search over one million articles, find something about almost anything!

Featured Article
 Kuru Kuru Kururin ... - but it rotates all the time, making the task difficult. The player controls the direction and speed of movement (it's a 3-speed stick). Gameplay is very challenging and ...