The Jacobi Symbol

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.  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].  We can 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), you have computed the legendre symbol, and you know whether a is a square mod n.