Jacobi symbol

From Academic Kids

The Jacobi symbol is used by mathematicians in the area of number theory. It is named after the German mathematician Carl Gustav Jakob Jacobi.

Definition

The Jacobi symbol is a generalization of the Legendre symbol using the prime factorization of the bottom number. It is defined as follows:

Let n > 2 be odd and n = <math>p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}<math>. For any integer a, the Jacobi symbol <math>\left(\frac{a}{n}\right) = \left(\frac{a}{p_1}\right)^{\alpha_1}\left(\frac{a}{p_2}\right)^{\alpha_2}\cdots \left(\frac{a}{p_k}\right)^{\alpha_k}<math>

Properties of the Jacobi symbol

There are a number of useful properties of the Jacobi symbol which can be used to speed up calculations. They include:

  1. If n is prime, the Jacobi symbol is the Legendre symbol.
  2. <math>

\left(\frac{a}{n}\right)\in \{0,1,-1\} <math>

  1. <math>

\left(\frac{a}{n}\right) = 0<math> if <math>\gcd (a,n) \neq 1<math>

  1. <math>

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

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

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

  1. <math>

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

  1. <math>

\left(\frac{-1}{n}\right) = (-1)^{\left(\frac{n-1}{2}\right)}<math> = 1 if n ≡ 1 (mod 4) and −1 if n ≡ 3 (mod 4)

  1. <math>

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

  1. <math>

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

The last property is known as reciprocity, similar to the law of quadratic reciprocity for Legendre symbols.

Residuals

The general statements about quadratic residuals with respect to the Legendre symbol cannot be made with the Jacobi symbol. However, if <math>\left(\frac{a}{n}\right) = -1<math> then a is not a quadratic residual of n because a was not a quadratic residual of some pk that divides n.

In the case where <math>\left(\frac{a}{n}\right) = 1<math> we are unable to say that a is a quadratic residual of n. Since the Jacobi symbol is a product of Legendre symbols, there are cases where two Legendre symbols evaluate to −1 and the Jacobi symbol evaluates to 1.de:Jacobi-Symbol fr:Symbole de Jacobi hu:Jacobi-szimbólum pl:Symbol Jacobiego

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