Jacobi symbol (another Prime Pages' Glossary entries)
 Glossary: Prime Pages: Top 5000: 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: (a|n)=0 if gcd(a,n) > 1. (-1|n) = 1 if n = 1 (mod 4), and (-1|n) = -1 if n = 3 (mod 4); (a|n) (b|n) = (ab|n); (a|m) (a|n) = (a|mn); if a = b (mod n), then (a|n) = (b|n). For the prime 2 we have (2|n) = 1 if n = 1 or 7 (mod 8), and (2|n) = -1 if n = 3 or 5 (mod 8). Finally, and perhaps most usefully, if gcd(a,n) =1, and a is odd and positive, In other words, (a|n)= (n|a), unless a = n = 3 (mod 4), in which case (a|n) = -(n|a). This gives the following algorithm for finding (a|n). Suppose n is odd and 0 < a < n: `````` Jacobi(a,n) { j := 1 while (a not 0) do { while (a even) do { a := a/2 if (n = 3 (mod 8) or n = 5 (mod 8)) then j := -j } interchange(a,n) if (a = 3 (mod 4) and n = 3 (mod 4)) then j := -j a := a mod n } if (n = 1) then return (j) else return(0) } `````` Notice that this is just an adaptation of the classical Euclidean algorithm. See Also: QuadraticResidue, LegendreSymbol Chris K. Caldwell © 1999-2018 (all rights reserved)