document.write (document.title)

 Math 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

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.