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

<math>
\frac{a}{p} = a^{\frac{p-1}{2}}\mod p </math>

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
Rameses

... IV[?] The name means "Child of the Sun". This is a disambiguation page; that is, one that just points to other pages that might otherwise have the s ...

 
 
 
This page was created in 29.2 ms