
Glossary: Prime Pages: Top 5000: 
The hardware and software on this system was updated September 4th.
Please let me know of any problem you encounter.
<caldwell@utm.edu> 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)
