• Quadratic reciprocity relates solutions to to solutions to , where p and q are distinct odd primes. The equations are both solvable or both unsolvable if either p or q has the form ; one is solvable and one is unsolvable if both primes have the form .
• Quadratic reciprocity can be expressed in terms of Legendre symbols: If p and q are distinct odd primes, then if either p or q has the form , whereas if both primes have the form .

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

that are greater than . 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. I'll use Gauss's lemma to compute .

Since , 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 says

As a check, Euler's theorem gives .

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

where or 1 and .

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 . , so , or . Since is not an integer, . Therefore, .

Example. Take and . , so the integer closest to is 2.

and .

Take and . , so the integer closest to is 3.

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 :

where 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 go 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 go mod 2. p and q are odd, so they equal 1 mod 2; , so either way it equals 1 mod 2. Therefore,

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

Now let , . Then , for implies --- 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? gives , or . That is, is negative for . So the product (for fixed n) has -1's, and

Now , so . In fact, , so . Since things which are equal mod 2 give the same power of -1,

Since the 's are just the integers from 1 to and since n runs from 1 to , ! So now I have

If I take the very first equation and go mod q, I get

( is invertible mod q, so the fraction makes sense.) So now

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,

In terms of 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 .

Next, I'll compute and .

Therefore, , and

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