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 ).
What about the 's?
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.
Copyright 2011 by Bruce Ikenaga