Jacobi symbol (another Prime Pages' Glossary entries)
 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. 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-2014 (all rights reserved)