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 
.
