The Jacobi symbol, written 
or 
is defined for positive odd 
as
 |
(1)
|
where
 |
(2)
|
is the prime factorization of 
and 
is the Legendre symbol.
(The Legendre symbol is equal to 
depending on whether 
is a quadratic residue
modulo 
.)
Therefore, when 
is a prime, the Jacobi symbol reduces to the Legendre
symbol. Analogously to the Legendre symbol, the Jacobi symbol is commonly generalized
to have value
 |
(3)
|
giving
 |
(4)
|
as a special case. Note that the Jacobi symbol is not defined for 
or 
even. The Jacobi symbol is
implemented in the Wolfram Language
as JacobiSymbol[n,
m].
Use of the Jacobi symbol provides the generalization of the quadratic reciprocity theorem
 |
(5)
|
for 
and 
relatively prime odd integers with 
(Nagell 1951, pp. 147-148). Written another way,
 |
(6)
|
or
 |
(7)
|
The Jacobi symbol satisfies the same rules as the Legendre symbol
 |
(8)
|
 |
(9)
|
 |
(10)
|
 |
(11)
|
 |
(12)
|
 |
(13)
|
Bach and Shallit (1996) show how to compute the Jacobi symbol in terms of the simple continued fraction of a rational
number 
.
