
Glossary: Prime Pages: Top 5000: 
Recall that the second (lower) entry in the Legendre
symbol (aq), also denoted , must be prime. Jacobi generalized the
Legendre symbol to allow lower entries that are odd (but
not necessarily prime) as follows: Let the factorization
of n be . Then
Notice that (a1) = 1 for all integers a. This new symbol (which looks just like the Legendre symbol) is called the Jacobi symbol. Warning: For the Jacobi symbol, (an)=1 does not necessarily mean that a is a quadratic residue of n. For example, (815) = 1, but 8 is not a quadratic residue of 15. The Jacobi symbol has many properties that make its use the easiest way to evaluate a Legendre symbol. Suppose m and n are positive odd integers, and a and b are any integers. Then the Jacobi symbol satisfies the following:
This gives the following algorithm for finding (an). Suppose n is odd and 0 < a < n: Notice that this is just an adaptation of the classical Euclidean algorithm.
See Also: QuadraticResidue, LegendreSymbol
Chris K. Caldwell © 19992014 (all rights reserved)
