Let be an odd prime. Let be the Legendre symbol: if is a quadratic residue modulo , if is a quadratic nonresidue and if divides . Let denote and let
As we’ll see below, it is not hard to show that , where . Figuring out the sign of , on the other hand, is a famously hard problem; Gauss struggled with it for over a year before a sudden insight, at which point he wrote:
Finally, two days ago, I succeeded – not on account of my hard efforts, but by the grace of the Lord. Like a sudden flash of lightning, the riddle was solved. I am unable to say what was the conducting thread that connected what I previously knew with what made my success possible.
The answer is that is a positive real number when and is a positive multiple of when is congruent to modulo . Gauss’s proof starts out by proving the following identity:
If is any primitive th root of unity, then
Here the exponents of on the right hand side are to be considered modulo . For example, if , the identity is
I tried to prove this the other day and, to my surprise, found that mathematical notation had proceeded far enough that it was no longer hard! I’m sure this argument isn’t original, but it is nice enough to go in a blog post.
Let’s define the polynomials
In general, my convention is that is an unspecified variable, is any primitive th root of unity and . The reason that it is hard to compute the sign of is that the sign of is different for different values of , and there are few results which distinguish the th roots of unity from each other. The essence of Gauss’s strategy is to reduce the problem to proving the identity , which does hold for any .
I will be using very little about : basically, that and Euler’s criterion, that . An easy consequence of the latter is that .
The computation of the sign of , using
First, let’s work out the sign of . Every factor is a pure imaginary number; it is a positive multiple of for odd and a negative multiple for even. So the product is either a positive multiple of or a positive real, according to whether is even or odd, as desired.
Now, let’s check that . We have
We know that , as both sides are monic polynomials of degree with the same roots. Plugging in , we get
Let’s also check that . It is convenient to start by computing
Rearranging the sum, this is
Let’s look at that inner sum. If , then it is . As ranges through , the quantity takes every value except and , once each. So this is . Meanwhile, if , then the inner sum is . So, in total, we have
We have which is so .
At this point, we know that so . We know that has the sign we want so, if we can prove , we win.
We already know that
and, if we can show that the sign is , we win. From now on, every occurrence of will represent this crucial sign.
I’m going to write the next paragraph in a pretty elementary way. I’m not never sure whether it is better to be simple or to be compact. The compact statement is “we work in .”
We know that is a root of . Since is irreducible, every is a root of . (If you don’t know how to show that is irreducible, here is an alternate route: show that and for any integer not divisible by . You might find Gauss’s lemma useful.) So divides , say . Since is monic, the coefficients of are integers and we can reduce this equation modulo . Also, once we reduce modulo , we have so . We conclude:
We make the shift of variables , and expand both sides in powers of . When remembering this proof, once you get this far, you are home free. The proof writes itself from here.
The right side is simpler. We have . (This equation, like the many that will follow, takes place in .) So
On the left hand side, we have
So the coefficient of is . It’s better to start by working out , and then extend by linearity. If you do some computations, you’ll probably guess the answer, so I’ll skip right to the proof.
Lemma: We have for , and .
Proof: Set . Choose in so that . So , and we conclude that . As for , this is with ones.
Corollary: We have for , and .
Proof: Combine the above lemma with Euler’s criterion.
So we see that the coefficient of in is for and the coefficient of is .
Putting it all together, we have
by Wilson’s theorem. We win.
We have it much easier than Gauss. First of all, I knew that some sort of identity like was true, although I didn’t remember the details. Discovering this result is surely the hardest part. Also, our notation is incomparably better: Gauss didn’t use the Legendre symbol, and didn’t work with congruences modulo polynomials. I’m not sure whether he would allow himself to work in the ring . Finally, many of us have seen a lot of the above computations before: The computations of and appear at the start of various cyclotomic proofs of quadratic reciprocity, some of them found by Gauss; the computation of modulo is the center of the proof of the Chevalley-Warning theorem.
Now that we have these advantages, the above proof can be summed up in two sentences. (1) It is easy to see that , so we just have to get the sign in . (2) Work -adically or, equivalently, -adically.
When we transform an art into a science, we aim to replace inspiration by perspiration.
Concrete Mathematics, Graham, Knuth and Patashnik