Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Number Theory > Theorems > Jacobi Symbol

Jacobi symbol

The Jacobi symbol is an extension of the Legendre symbol to any odd modulus, using the rule (a/bc) = (a/b)(a/c) to decompose the modulus as a product of primes.

If a is an integer and n>0 is odd, then  ( a

n
)  =  ( a

p1
) e1

 
( a

p2
) e2

 
... ( a

pk
) ek

 
, where

p1e1, p2e2, ..., pkek is the prime factorization of n, and (a/pi) are Legendre Symbols.

Alternatively,

If a is an integer and n>0 is odd, then  ( a

n
)  =  ( a

p1
) ( a

p2
) ... ( a

pk
) , where

p1, p2, ..., pk are all the primes dividing n/s, where s is the largest square factor of n, and (a/pi) are Legendre Symbols.

 Still another formulation is

If a is an integer and n>0 is odd, then  ( a

n
)  is  {

0 if GCD(a,n)≠1,
-1 if Legendre(a|pi)=-1 for an odd number of prime factors, pi,
1 otherwise

Quadratic residue

A consequence of this last formulation of the Jacobi Symbol is that if (a/n)=-1, then a is for sure not a quadratic residue (mod n); however, if (a/n)=1, then a may or may not be a quadratic residue (mod n).  Examples of this phenomenon include:

(2/3)=-1 and (2/5)=-1, so 2 is not a quadratic residue (mod 15), yet (2/15)=1.

(2/7)=1 and (2/17)=1, so 2 is a quadratic residue (mod 119), and (2/119)=1.

So in these two cases, (2/15)=1 and (2/119)=1, so if the (a/n)=1, then a may or may not be a quadratic residue (mod n).

If a,n are not coprime, then Jacobi (a/n)=0, and, again, a may or may not be a quadratic residue (mod n).

Internet references

Mathworld: Jacobi Symbol

Prime Glossary: Jacobi Symbol

Wikipedia: Jacobi symbol

Related pages in this website

Jacobi Symbol Algorithm -- programs written in pseudocode, Javascript, VBA (Microsoft Visual Basic for Applications)

Legendre symbol —  ( a

p
)  , where a is any integer, and p is an odd prime
Kronecker symbol —  ( a

n
)  , where a and n are any integers, an extension of the Jacobi symbol.

The webmaster and author of this Math Help site is Graeme McRae.