Jacobi symbol
(another Prime Pages' Glossary entries)
The Prime Glossary
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 (a|q), also denoted (a|q), 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 p1^e1. p2^e2. p3^e3. . . . .pk^ek. Then

(a|n) = (a|p1)^e1.(a|p2)^e2.(a|p3)^e3. . . . .(a|pk)^ek
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,
  • (a|b)(b|a)=(-1)^...
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)