The Jacobi Symbol

It's a little inconvenient that the Legendre symbol is only defined when the bottom is an odd prime. You can extend the definition to allow an odd positive number on the bottom using the Jacobi symbol. Most of the properties of Legendre symbols go through for Jacobi symbols, which makes Jacobi symbols very convenient for computation. We'll see, however, that there is a price to pay for the greater generality: Euler's formula no longer works, and we lose part of the connection between the value of a symbol and the solvability of the corresponding quadratic congruence.

Definition. Let , where and q is a product of odd primes:

(The need not be distinct.) The Jacobi symbol is defined by

Note that the Jacobi symbol and the Legendre symbol coincide in the case where q is a single odd prime. That is why the same notation is used for both. It's clear from the definition that .

Lemma. If q is a product of odd primes and a is a quadratic residue mod q, then .

Proof. Write , where each is an odd prime. Suppose a is a quadratic residue mod q. Then and has solutions.

Since , it follows that and for . Hence, for . Therefore,

However, the converse is false: If is a Jacobi symbol and , it does not follow that p is a quadratic reside mod q.

Example. Show that , but 2 is not a quadratic residue mod 15.

Since 2 is not a square mod 3 or mod 5,

Therefore,

However, here is a table of squares mod 15:

The table shows that 2 is not a square mod 15. The quadratic residues mod 15 are 1 and 4, as those are the squares that are relatively prime to 15.

The results that follow amount to saying that the algebraic properties of Legendre symbols hold for Jacobi symbols --- and indeed, the proofs of these properties typically use those properties for Legendre symbols.

Theorem. Let q and be odd positive numbers, and suppose . Then:

(a) .

(b) .

(c) .

(d) .

(e) If , then .

Proof. (a) Write q and as products of odd primes:

Then

(b) Write q as a product of odd primes:

Then

(c) Write q as a product of odd primes:

If is an odd prime, then (as a Legendre symbol). Hence,

Next, observe that if is an odd prime, then

So

(d)

(e) Write q as a product of odd primes:

Since , I have for . Consequently, (as Lengendre symbols). Therefore,

Example. Show that if and q is odd and positive, it does not follow that

(Thus, the analog of Euler's lemma does not hold for Jacobi symbols.)

Note that

But

The next lemma will be used in the proofs of the formulas for and , as well as in the proof that Quadratic Reciprocity holds for Jacobi symbols.

Lemma. If m and n are odd, then

Proof. Since m and n are odd, I may write

Then

On the other hand,

Corollary. If are odd, then

Proof. Use the previous lemma and induction.

The way this corollary will be used in the following proof is the simple observation that if , then .

Theorem. Let q be an odd positive number. Then

Proof. Write q as a product of odd primes:

Then

The terms on the right are Legendre symbols, for which I know

Thus,

Using the preceding corollary,

Therefore,

Theorem. (Quadratic Reciprocity) Suppose p and q are odd positive integers and . Then

Proof. I'll prove the equivalent statement

(To get from either this statement to the original one or vice versa, multiply both sides by and note that .)

Write p and q as products of odd primes:

Then

Here's what the last double product looks like, multiplied out:

By Quadratic Reciprocity for Legendre symbols,

Taking the product over i and j on both sides, I get

Taking the product of powers of -1 causes the powers to add. So

By the preceding corollary,

That is,

Hence,

Remark. In computational terms, this version of reciprocity is like the one for Legendre symbols. Thus, suppose p and q are odd and relatively prime. If either p or q equals 1 mod 4, then

If both p and q equal 3 mod 4, then

Next, I'll derive a formula for , where q is an odd prime. The proof is similar to the proof of the formula for , except that I have slightly different preliminary lemmas.

Lemma. If m and n are odd, then

Proof. Since m and n are odd, I may write

Then

So

(Note that is even because it's the sum of two odd numbers, so is an integer. Likewise, is an integer.)

Now

Corollary. If are odd, then

Proof. Use the previous lemma and induction.

Theorem. Let q be an odd positive number. Then

Proof. Write q as a product of odd primes:

Then

The terms on the right are Legendre symbols, for which I know

Thus,

Using the preceding corollary,

Therefore,

Example. Compute the Jacobi symbol .

Example. Compute the Legendre symbol .

Jacobi symbols can often be used to simplify the computation of Legendre symbols.

Contact information