TOPICS
Search

Jacobi Symbol


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

 (n/m)=(n/(p_1))^(a_1)(n/(p_2))^(a_2)...(n/(p_k))^(a_k),
(1)

where

 m=p_1^(a_1)p_2^(a_2)...p_k^(a_k)
(2)

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,
(3)

giving

 (n/n)=0
(4)

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

 (m/n)(n/m)=(-1)^((m-1)(n-1)/4)
(5)

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

 (m/n)=(-1)^((m-1)(n-1)/4)(n/m)
(6)

or

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

The Jacobi symbol satisfies the same rules as the Legendre symbol

 (n/m)(n/(m^'))=(n/((mm^')))
(8)
 (n/m)((n^')/m)=(((nn^'))/m)
(9)
 ((n^2)/m)=(n/(m^2))=1    if (m,n)=1
(10)
 (n/m)=((n^')/m)    if n=n^' (mod m)
(11)
 ((-1)/m)=(-1)^((m-1)/2)={1   for m=1 (mod 4); -1   for m=-1 (mod 4)
(12)
 (2/m)=(-1)^((m^2-1)/8)={1   for m=+/-1 (mod 8); -1   for m=+/-3 (mod 8)
(13)

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

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

Explore with Wolfram|Alpha

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

Subject classifications