|
|
|
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, |
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).
Mathworld: Jacobi Symbol
Prime Glossary: Jacobi Symbol
Wikipedia: Jacobi symbol
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.