info prev up next book cdrom email home

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

\end{displaymath} (1)

\end{displaymath} (2)

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

(n/m)=(n'/m) \qquad {\rm if\ } n\equiv n'\ \left({{\rm mod\ } {m}}\right)
\end{displaymath} (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}
\end{displaymath} (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}
\end{displaymath} (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}
\end{displaymath} (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).
\end{displaymath} (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


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.

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein