Jacobi symbol

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

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:

For the prime 2 we have

Finally, and perhaps most usefully, if gcd(a,n) =1, and a is odd and positive,

In other words, (a|n)= (n|a), unless an ≡ 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

Printed from the PrimePages <t5k.org> © Reginald McLean.