Legendre symbol

From Academic Kids

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 a prime number and a is an integer, then the Legendre symbol <math>\left(\frac{a}{p}\right)<math> 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 k2a (mod p), or a is a quadratic residue modulo p
  • −1 if a is not a square modulo p, or 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:

  1. <math>

\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) <math> (it is a completely multiplicative function in its top argument)

  1. If ab (mod p), then <math>

\left(\frac{a}{p}\right) = \left(\frac{b}{p}\right) <math>

  1. <math>

\left(\frac{1}{p}\right) = 1 <math>

  1. <math>

\left(\frac{-1}{p}\right) = (-1)^{\left(\frac{p-1}{2}\right)}<math>, i.e. = 1 if p ≡ 1 (mod 4) and = −1 if p ≡ 3 (mod 4)

  1. <math>

\left(\frac{2}{p}\right) = (-1)^{\left(\frac{p^2-1}{8}\right)}<math>, i.e. = 1 if p ≡ 1 or 7 (mod 8) and = −1 if p ≡ 3 or 5 (mod 8)

  1. <math>

\left(\frac{a}{2}\right)<math> = 1 for all odd a and 0 for all even a

  1. If q is an odd prime then <math>

\left(\frac{q}{p}\right) = \left(\frac{p}{q}\right)(-1)^{\left(\frac{p-1}{2}\right)\left(\frac{q-1}{2}\right)} <math>

The last property is known as the law of quadratic reciprocity.

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

<math>

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

Additionally, the Legendre symbol is a Dirichlet character.

Related functions

The Jacobi symbol is a generalization of the Legendre symbol that allows composite bottom numbers.de:Legendre-Symbol es:Símbolo de Legendre fr:Symbole de Legendre it:Simbolo di Legendre pl:Symbol Legendre'a sv:Legendresymbolen

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools