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.

Copyright 2017 by Bruce Ikenaga