Jacobi Symbol

The product of Legendre Symbols $(n/p_i)$ for each of the Prime factors $p_i$ such that $m=\prod_i p_i$, denoted $(n/m)$. When $m$ is a Prime, the Jacobi symbol reduces to the Legendre Symbol. The Jacobi symbol satisfies the same rules as the Legendre Symbol

$$(n/m)(n/m')=(n/(mm'))$$ (1)

$$(n/m)(n'/m)=((nn')/m)$$ (2)

$$(n^2/m)=(n/m^2)=1 \qquad {\rm if\ } (m,n)=1$$ (3)

$$(n/m)=(n'/m) \qquad {\rm if\ } n\equiv n'\ \left({{\rm mod\ } {m}}\right)$$ (4)

$$(-1/m)=(-1)^{(m-1)/2}=\cases{ 1 & for $m\equiv 1\ \left({{\r... ...$\cr -1 & for $m\equiv -1\ \left({{\rm mod\ } {4}}\right)$\cr}$$ (5)

$$(2/m)=(-1)^{(m^2-1)/8}=\cases{ 1 & for $m\equiv \pm 1\ \left... ...r -1 & for $m\equiv \pm 3\ \left({{\rm mod\ } {8}}\right)$\cr}$$ (6)

$$(n/m)=\cases{ (m/n) & for $m{\rm\ or\ }n\equiv 1\ \left({{\r... ...(m/n) & for $m,n\equiv 3\ \left({{\rm mod\ } {4}}\right)$.\cr}$$ (7)

Written another way, for $m$ and $n$ Relatively Prime Odd Integers with $n\geq 3$,

$$(m/n)=(-1)^{(m-1)(n-1)/4} (n/m).$$ (8)

The Jacobi symbol is not defined if $m\leq 0$ or $m$ is Even.

Bach and Shallit (1996) show how to compute the Jacobi symbol in terms of the Simple Continued Fraction of a Rational Number $a/b$.

See also Kronecker Symbol

References

Bach, E. and Shallit, J. Algorithmic Number Theory, Vol. 1: Efficient Algorithms. Cambridge, MA: MIT Press, pp. 343-344, 1996.

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.

Riesel, H. ``Jacobi's Symbol.'' Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 281-284, 1994.