Recall that the second (lower) entry in the Legendre
symbol (a|q), 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 (a|1) = 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, (a|n)=1 does not necessarily mean that a is a quadratic residue of n. For example, (8|15) = 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 (a|n). Suppose n is odd and 0 < a < n:
Notice that this is just an adaptation of the classical Euclidean algorithm.