Jacobi Symbol

The Jacobi symbol, written (n/m) or (n/m) is defined for positive odd m as




is the prime factorization of m and (n/p_i) is the Legendre symbol. (The Legendre symbol is equal to +/-1 depending on whether n is a quadratic residue modulo m.) Therefore, when m 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

 (n/m)=0  if GCD(m,n)!=1,



as a special case. Note that the Jacobi symbol is not defined for m<=0 or m 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


for m and n relatively prime odd integers with n>=3 (Nagell 1951, pp. 147-148). Written another way,



 (n/m)={(m/n)   for m or n=1 (mod 4); -(m/n)   for m,n=3 (mod 4).

The Jacobi symbol satisfies the same rules as the Legendre symbol

 ((n^2)/m)=(n/(m^2))=1    if (m,n)=1
 (n/m)=((n^')/m)    if n=n^' (mod m)
 ((-1)/m)=(-1)^((m-1)/2)={1   for m=1 (mod 4); -1   for m=-1 (mod 4)
 (2/m)=(-1)^((m^2-1)/8)={1   for m=+/-1 (mod 8); -1   for m=+/-3 (mod 8)

Bach and Shallit (1996) show how to compute the Jacobi symbol in terms of the simple continued fraction of a rational number n/m.

See also

Kronecker Symbol, Legendre Symbol, Quadratic Residue

Related Wolfram sites

Explore with Wolfram|Alpha


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.

Subject classifications