Theorem. ( Gauss's Lemma) Let p be an odd prime, . Let k be the number of least positive residues of

Then

Proof. Since p is odd, is not an integer. Hence, every residue of a, , ..., is either less than or greater than . Label these two sets:

Thus, .

Step 1 .

The 's are contained in , because the 's are less than (so less than or equal to ).

Since is an integer and is an integer plus one-half, I have . This shows that the 's are contained in as well.

There are elements in , and . So if the 's and 's are all distinct, I'll know the two sets are equal.

Each has the form , where . So if and are the same, then

, so . This is impossible for unless --- which implies to begin with.

A similar argument shows that the 's, and hence the 's, are distinct.

Could ? and for , so

Again, , so . But implies , so is impossible.

This finishes the proof that .

Step 2 Since the two sets are the same, the products of the elements in the two sets are the same:

Now , so

But the a's and b's are exactly the residues of the numbers , so I may replace the product of the a's and b's with the product of :

Now , so I can cancel the terms from both sides. Then applying Euler's theorem, I get

I made the last step by multiplying both sides by and using the fact that .

Example. Use Gauss's Lemma to compute .

Since , I have and . Look at the residues , , and . All three are greater than 3.5 --- they're 's, in the notation of the proof of Gauss's Lemma --- so Gauss's Lemma says

As a check, Euler's theorem gives .

The following technical lemma will be needed for the proof of reciprocity.

Lemma. Let , where b is an odd integer. Then

Here denotes the greatest integer function and is the integer closest to .

Proof. By the Division Algorithm,

Now is not an integer, so either or .

(For example, if and , then , while if and , .)

Consider the two cases.

Case 1: .

Write

Here , and is the integer closest to . , but is not an integer, so , and .

Case 2: .

Write

Here , and is the integer closest to . , so . Now , so , or . Since is not an integer, . Therefore, .

Example. Illustrate the lemma with:

(a) and .

(b) and .

(a) For and , I have , so the integer closest to is 2. Then

And .

(b) For and , I have , so the integer closest to is 3. Then

And .

In other words, the r in the lemma represents the distance from a to the nearest multiple of b.

The is needed depending on whether the nearest multiple is less than or greater than a.

I'll use the lemma to give an ingenious proof of Quadratic Reciprocity due to J.S.~Frame [1].

Theorem. ( Quadratic Reciprocity) Let p and q be distinct odd primes.

Proof. To simplify the writing, let and .

Let . Apply the Lemma with and :

Here and or 1.

The first thing I will show is that the remainders are just a permutation of the integers 1, ..., .

If I take the initial equation and reduce mod q, I get

Can two of the r's be equal? Suppose , where . Then

In other words, . But , so is surely smaller than q in absolute value. Since , this is impossible unless . This in turn is impossible unless . Thus, the r's are distinct. Since there are of them, and since they're all in the range , they must be some permutation of the numbers 1, ..., .

As a preliminary to the next computation, take the first equation and reduce mod 2. Now p and q are odd, so they equal 1 mod 2. Also, , and it both cases . Therefore,

(I'm going to use this in an exponent of -1 in a second!)

Now let , . Then , for implies --- which is impossible, because .

Now here's the heart of the proof. The idea will be to define a weird product which turns out to be the Legendre symbol. Define

Notice that is a fancy way of expressing the sign of --- when it's positive, -1 when it's negative.

When is negative?

That is, is negative for . So the product for for fixed n has terms equal to -1, and

(The terms equal to 1 contribute nothing to the product.)

Now

The last equality comes from the fact that .

Now if then . So

Since the 's are just the integers from 1 to and since n runs from 1 to , the sum of the 's is the same as the sum of the n's from 1 to , and

So the previous equation becomes

Recall from above that

Now is invertible mod q, so I may write

Plugging this into the last equation for , I get

But , because as n runs over the numbers from 1 to , so does . So by Euler's theorem,

Notice that

I got the second product by swapping m and n in the first.

Whew! The rest is easy --- fortunately!

Since and , I'm done!

As complicated as this proof is, it's actually no worse than most proofs of this result.

Before giving an example, I want to discuss what reciprocity tells you about solutions to quadratic congruences.

An odd prime p is congruent to 1 or to 3 mod 4.

If , then , an even number. If , then , an odd number.

Since an even number times anything is even,

Therefore,

However,

Consider the congruences

This means:

1. If at least one of p, q is congruent to 1 mod 4, then both equations are solvable or both equations are unsolvable.

2. If both p and q are congruent to 3 mod 4, then one equation is solvable and the other is unsolvable.

Corollary. Let p and q be distinct odd primes.

(a) If at least one of p, q is congruent to 1 mod 4, then

(b) If both p and q are congruent to 3 mod 4, then

Example. Compute .

, so

In other words, does not have any solutions.

Example. Compute .

I'll compute and . First,

Next,

Next, I'll compute and .

Therefore, , and

In other words, the congruence does not have a solution.

[1] J.S. Frame, A short proof of quadratic reciprocity, Amer. Math. Monthly, 85(10)(1978), 818--819.

Contact information