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 .