Modular Mathematics, The Jacobi Symbol

The Jacobi Symbol

If n is odd, the jacobi symbol [a\n], which looks exactly like the legendre symbol, is the product [a\q] for all prime factors q in n, including multiplicities. Thus [a\n] = 0 iff a and n have a common factor q. Unlike the legendre symbol, the value of the jacobi symbol does not tell you whether a is a square mod n.

Since multiplication distributes over the legendre symbol, it also distributes over the jacobi symbol. That is, [a\n]×[b\n] = [ab\n]. Use this in reverse to write [a\n] as the product of [p\q] for all primes p in a and q in n, including multiplicities.

If the jacobi symbol is split apart, as above, assume there are k primes in a that are 3 mod 4, and l primes in n that are 3 mod 4. Flip the legendre symbols over and follow the quadratic reciprocity law, bringing in kl factors of -1. This is -1 iff kl is odd iff a and n are both 3 mod 4. Therefore quadratic reciprocity is valid for jacobi symbols.

Show that [2,n] and [-1,n] can be evaluated by looking ad n mod 4 and mod 8, as though they were legendre symbols.

One does not need to factor a or n to determine [a\n]. Perform a procedure similar to Euclid's gcd algorithm, keeping ±1 in an accumulator. Divide the bottom into the top, take the remainder, pull out factors of 2 (adjusting the accumulator), and flip (adjusting the accumulator). When the top becomes 1, you are done.

If n happens to be prime (at the start), then the original jacobi symbol [a\n] is itself a legendre symbol. You have computed the legendre symbol, and you know whether a is a square mod n.

Jacobi Example

For grins, here is the math to see if a million and 7 is a square mod a billion and 7. (1000000007 is a prime number.)

1000007 mod 1000000007

Both numbers are 3 mod 4, so negate the accumulator as you flip
1000000007 mod 1000007 sign -1

reduce
993014 mod 1000007

Numbers have to be odd, so divide the top by 2.
The bottom is 7 mod 8, so 2 is a square, and nothing changes.
496507 mod 1000007

1000007 mod 496507 sign 1

6993 mod 496507

496507 mod 6993

4 mod 6993

4 is a square, so we're done. The accumulator holds 1, so 1000007 is a square mod 1000000007; though we have no idea the square root, unless we search through all billion numbers to find it.

Composite n

The jacobi symbol does not correspond to a quadratic residue when n is composite. Intuitively, let n = 77 = 7 times 11. By the chinese remainder theorem, these run as separate rings. Half the coprime elements are squares mod 7, and half are squares mod 11, so one fourth are squares mod 77. Yet the jacobi symbol is 1 half the time.

Even when n is a prime power we can get into trouble. Let n = qk where q is prime and k is even. Let z be a number strictly between 1 and q, and consider [z\n]. This is [z\q] to an even power, and is 1. Now look at the multiplicative group mod n. It is cyclic, hence z is a square iff its discrete log is even. A group homomorphism takes the units mod n onto the units mod p. This effectively reduces the discrete log mod p-1. Subtracting a multiple of an even number from log(z) will not change the parity of log(z). In other words, z is a square mod n iff z is a square mod p. So let z be a nonsquare mod p, and a nonsquare mod n, and the jacobi symbol is not accurate; since it says [z\n] = 1.

Pulling out Squares

Write [a\n] as a product of jacobi symbols, separating the numerator into its primes. If the numerator contains a square, such as p2, pull out [p\n][p\n]. This is 1, and drops away. Thus all squares can be pulled out of the numerator. In the same way, all squares can be pulled out of the denominator.