# Jacobi symbol

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 = [itex]p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}[itex]. For any integer a, the Jacobi symbol [itex]\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}[itex]

## 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. [itex]

\left(\frac{a}{n}\right)\in \{0,1,-1\} [itex]

1. [itex]

\left(\frac{a}{n}\right) = 0[itex] if [itex]\gcd (a,n) \neq 1[itex]

1. [itex]

\left(\frac{ab}{n}\right) = \left(\frac{a}{n}\right)\left(\frac{b}{n}\right) [itex]

1. If ab (mod n), then [itex]

\left(\frac{a}{n}\right) = \left(\frac{b}{n}\right) [itex]

1. [itex]

\left(\frac{1}{n}\right) = 1 [itex]

1. [itex]

\left(\frac{-1}{n}\right) = (-1)^{\left(\frac{n-1}{2}\right)}[itex] = 1 if n ≡ 1 (mod 4) and −1 if n ≡ 3 (mod 4)

1. [itex]

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

1. [itex]

\left(\frac{m}{n}\right) = \left(\frac{n}{m}\right)(-1)^{\left(\frac{m-1}{2}\right)\left(\frac{n-1}{2}\right)} [itex]

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 [itex]\left(\frac{a}{n}\right) = -1[itex] 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 [itex]\left(\frac{a}{n}\right) = 1[itex] 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)