Let be an odd prime. I’ll now show how sums over complex roots of unity can be used to show the law of quadratic reciprocity, which states that being a square mod is related to whether is a square mod .
Let be the Legendre symbol: it takes on the value 0 if is 0, if is a square mod , and otherwise. We’ll be seeing what happens when you sum up some complex roots of unity and square the resulting value. I am following the proof given in A Classical Introduction to Modern Number Theory, Ireland and Rosen.
Summing Complex Roots of Unity
Let be a complex -th root of unity . The quadratic Gaussian sum is the value .
Why might this be useful? It’s not hard to show that for all , , meaning that we can recover the value by knowing the value of .
For example, when :
2 and 3 are non-residues mod 5, so the sign of the quadratic Gaussian sum and is negative.
Proof: We only consider the case where is coprime to .
(Because is a prime and is coprime to , must take on all values mod ). Multiplying both sides by gives the desired result.
Proof: To show this, we evaluate in two different ways. Again we only focus on coprime to .
First, by the previous lemma, we have . Summing over all gives us .
Direct expansion gives:
When summing this term over , terms where vanish, since these end up summing over all roots of unity. For each , when , there are terms. Therefore:
Therefore . Cancelling terms of and multiplying both sides by gives the desired result. (By Fermat’s little theorem we have .)
We are in a place to prove the law of quadratic reciprocity, which links the values and .
If either or are , the right hand side is , and is a residue in if and only if is a residue in . Let and - it happens that . is a square mod () and is a square mod ().
However, if both and are , then the relationship is flipped: is a residue in if and only if is not a residue in . For example, and : and 2 is a square mod (, but is not a square mod .
Proof: Let . By the above lemma we have . Take , another odd prime. Then we have:
Multiplying both sides by gives:
Since we are examining congruences modulo , we can “push” the exponent down into the sum, giving, as per our first lemma. Therefore we have:
The value can be seen to equal as : therefore is a residue mod if both and are residues mod or they are both non-residues. Arranging terms gives the desired result.
Quadratic reciprocity is what really hooked me on my study of the Ireland and Rosen textbook. The previous few chapters had been about congruences and the structure of subrings of integers - interesting stuff but sort of dry, and not too different from the standard abstract algebra I had covered in undergrad.
However, this theorem sort of came out of left field: it seemed strange that being a square mod would be related at all to being a square mod - especially given that one of these numbers is larger than the other! (When you talk about being a square mod , it’s actually a statement about ’s coset in the integers mod .)
There are a few different proofs presented in the textbook, but the presentation of quadratic Gaussian sums struck me as exceptionally simple. The Legendre symbol initially seemed to me as a strange thing to include in the sum terms, but it can be shown that the Legendre symbol is just an example of a multiplicative character, which maps a finite field into the unit circle in a way that preserves multiplication. The unit circle hooked me on trigonometry back in high school and I love seeing it appear again and again.