TOPICS

# Jacobi Symbol

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 .

Kronecker Symbol, Legendre Symbol, Quadratic Residue

## Related Wolfram sites

http://functions.wolfram.com/NumberTheoryFunctions/JacobiSymbol/

## Explore with Wolfram|Alpha

More things to try:

## References

Bach, E. and Shallit, J. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. Cambridge, MA: MIT Press, pp. 343-344, 1996.Bressoud, D. M. and Wagon, S. A Course in Computational Number Theory. London: Springer-Verlag, p. 189, 2000.Guy, R. K. "Quadratic Residues. Schur's Conjecture." §F5 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 244-245, 1994.Nagell, T. "Jacobi's Symbol and the Generalization of the Reciprocity Law." §42 in Introduction to Number Theory. New York: Wiley, pp. 145-149, 1951.Riesel, H. "Jacobi's Symbol." Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 281-284, 1994.

## Cite this as:

Weisstein, Eric W. "Jacobi Symbol." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/JacobiSymbol.html