In this post, I’d like to explain a proof of the Law of Quadratic Reciprocity based on properties of Lucas polynomials. (There are over 300 known proofs of the Law of Quadratic Reciprocity in the literature, but to the best of my knowledge this one is new!)
In order to keep this post as self-contained as possible, at the end I will provide proofs of the two main results (Euler’s criterion and the Fundamental Theorem of Symmetric Polynomials) which are used without proof in the body of the post.
Lucas polynomials
The sequence of Lucas polynomials is defined by , , and for
The next few terms in the sequence are , and .
By induction, the degree of is equal to . The integers are the Lucas numbers, which are natural “companions” to the Fibonacci numbers (see, e.g., this blog post).
The polynomials
It’s easy to see that for odd, is divisible by and has only even-power terms. Thus for some monic integer polynomial of degree . We will be particularly interested in the polynomials for prime.
If is even (resp. odd), a simple induction shows that the constant term (resp. the coefficient of ) in is equal to . In particular, for odd we have .
Resultants
Given two monic polynomials and with integer coefficients and roots , their resultant is defined to be
The only nontrivial fact we will use about the resultant is the following:
Theorem 1: Given a monic polynomial and a positive integer , there is a polynomial such that for every polynomial
The polynomial can be computed explicitly as the determinant of a certain Sylvester matrix (see Theorem 43.2 of this book for a proof). However, for our proof of Quadratic Reciprocity we don’t need an explicit formula for this polynomial, we just need to know that exists, and this is a simple application of the Fundamental Theorem of Symmetric Polynomials (see the Appendix for a proof).
Using Theorem 1, we see that:
(R1) The resultant of and belongs to .
(R2) If is another monic polynomial of degree and the coefficients of and are congruent modulo (which we write as ) for some positive integer , then .
It is immediate from the definition that:
(R3)
(R4)
Two observations
Our proof of the Law of Quadratic Reciprocity will be based on the following two simple observations:
Proposition 1: For every prime , we have Equivalently,
Proposition 2: If are distinct odd primes then .
Proof of the Law of Quadratic Reciprocity
Assuming Propositions 1 and 2 for the moment, we now explain how they imply the Law of Quadratic Reciprocity.
If is prime and is an integer not divisible by , the Legendre symbol is defined to be 1 if is a quadratic residue mod and -1 otherwise.
Theorem (Law of Quadratic Reciprocity): If are distinct odd primes than
Proof: Let be distinct odd primes. By Proposition 1, (R2), and (R3) we have Since and by Euler’s criterion, we have But by Proposition 2, so By symmetry, we also have So by (R4),
Proof of Proposition 1
We claim that for all ,
(L1)
This easily implies Proposition 1. Since the claim holds for and by inspection, it suffices to show that the right-hand side satisfies the same recursion as the Lucas polynomials. This is equivalent to proving the identity for . But this is a straightforward algebraic exercise: just multiply both sides of the readily verified identity by
Further properties of Lucas polynomials and resultants
Our proof of Proposition 2 will make use of the following formulas:
(L2) for all , where and .
(This is a generalization of the Binet formula for the Lucas numbers, where is the golden ratio.)
(L3) for all .
(This also generalizes a well-known property of Lucas numbers.)
(R5) If with monic integer polynomials then
To prove (L2), it suffices to note that and therefore for all , and similarly for . Since (L2) holds for and by inspection, the identify follows for all by induction.
To prove (L3), note that Since , (L3) follows from (L2).
To prove (R5), note from (R3) that since and for all .
Proof of Proposition 2
Note first that (L3) implies that when is odd and is even we have
and similarly when is odd and is even we have
We claim that if are odd positive integers with and then We will show this by induction on . For we have and the result is clear. For the inductive step, write with even and note that from (R5),
Furthermore, since any common divisor of and will also divide and hence . By induction, and the claim follows.
This completes our proof of the Law of Quadratic Reciprocity.
Relation to other proofs
The zeros of are for (see this paper for a proof). Using this, one can show that when is prime, is the minimal polynomial of , where is a primitive root of unity. (Note that Proposition 1 and the fact that show that is irreducible by Eisenstein’s criterion.) Thus our proof is closely related to the argument described in this Math Overflow post by Antoine Chambert-Loir, with in our proof equal to in loc. cit.
This may help clarify what’s “really going on” in our proof. However, by removing all mention of complex roots of unity and basing our calculations on the recursive formula for Lucas polynomials instead of the identity , we have made the proof more elementary and perhaps more accessible for undergraduate students studying number theory for the first time.
By the same token, our proof is closely related to Eisenstein’s classical proof of the Law of Quadratic Reciprocity based on trigonometric functions. But again, our proof is somewhat simpler in that it does not require any knowledge of real or complex analysis.
See Section 3.4 of this paper for additional remarks about various other proofs of the Law of Quadratic Reciprocity which ultimately boil down (either explicitly or in disguise) to property (R4) of resultants.
Concluding remarks
(1) One could avoid the need to appeal to Theorem 1 in our proof of Quadratic Reciprocity by defining the resultant to be the expression given by Sylvester’s determinant and establishing the necessary properties directly from this definition. For (R1) and (R2) this is clear, (R4) is easy, and (R5) follows by applying elementary row operations. Instead of proving (R3) in general, note that in our proof of Quadratic Reciprocity we only need to apply (R3) when (which is congruent to modulo ), and this special case follows easily from the determinental formula for the resultant. I think that it would be a pedagogical disaster to rewrite the proof in this way, but it’s nice to know that it can be done.
(2) There are also polynomial analogues of the Fibonacci numbers, and many of the standard identities and formulas relating Fibonacci and Lucas numbers have extensions to the polynomial setting. See, for example, this Wikipedia page.
(3) Our proof of Proposition 2 showed that if are odd positive integers with and then Conversely, if one can show (using the fact that forms an odd divisibility sequence, as mentioned here) that
Resultants of Lucas polynomials (and various analogues) are discussed in detail in this paper, and in particular Proposition 2 in this post can be deduced from the formula given in Table 3 of loc. cit.
(4) One can give an alternate proof of Proposition 1 using (L2) and the binomial theorem. We leave the details to the interested reader.
(5) For two more proofs of Quadratic Reciprocity, see https://mattbaker.blog/2013/07/03/quadratic-reciprocity-and-zolotarevs-lemma/ and https://mattbaker.blog/2015/04/30/the-sign-of-the-quadratic-gauss-sum-and-quadratic-reciprocity/
If that’s not enough for you, see this blog post by Antoine Chambert-Loir.
Appendix: Proofs of Euler’s Criterion and the Fundamental Theorem of Symmetric Polynomials
Proof of Euler’s Criterion
We present an argument (adapted from this Wikipedia page) which is more elementary than the usual proofs based on primitive roots or Lagrange’s theorem on the number of roots of a polynomial modulo . This argument (which deserves to be better known) proves, in one fell swoop, Euler’s criterion, Wilson’s theorem, and Fermat’s Little Theorem.
Lemma: If is an odd prime and is a non-zero quadratic residue modulo then there are precisely 2 solutions (modulo ) to .
Proof: Since is a quadratic residue, there exists such that . The congruence is equivalent to , which implies that or . Thus or . Since and , we have as well and thus .
Theorem (Euler’s Criterion): If is an odd prime and is an integer not divisible by , then is congruent to 1 modulo if is a quadratic residue mod and to if is not a quadratic residue mod .
Proof: Let denote the set modulo , and let . By the lemma, there are precisely quadratic residues and non-residues modulo , since the map given by is 2-to-1 and its image is precisely the set of quadratic residues mod .
Given , define by . Then for all and is an involution, i.e., iff . Note that iff .
If is not a quadratic residue, we have for all . In this case, pairing to gives a grouping of all elements of into distinct pairs, with the elements of each pair multiplying to modulo . Thus .
If is a quadratic residue, the grouping works in the same way except that there are (by the Lemma) precisely two pairs with , namely the two square roots of modulo . Since , we have .
In terms of the Legendre symbol, this gives for all Setting shows that (Wilson’s theorem), and thus for all (Euler’s criterion).
As a bonus, squaring both sides in Euler’s criterion gives (Fermat’s Little Theorem).
Proof of the Fundamental Theorem of Symmetric Polynomials
We present a proof adapted from these lecture notes by Paul Garrett. (For a different proof, see this handout by Keith Conrad.)
Theorem (Fundamental Theorem of Symmetric Polynomials): If is invariant under all permutations of the variables , then there is a polynomial such that , where are the elementary symmetric polynomials in .
Proof: Let be the degree of as a polynomial in . The proof is by induction on and the number of variables . If or the result is trivial. Now assume the result is true for polynomials of degree smaller than and for polynomials in fewer than variables, and define by Then is invariant under permuting , so by induction there is an integer polynomial in variables such that
Let be the corresponding polynomial in the symmetric functions of one additional variable. Then , so , considered as a polynomial in with coefficients in , has a zero at , and thus divides . Since and are both symmetric in , so is , and therefore divide as well. So is divisible by the product .
Define . Since either or the maximum degree of is strictly less than the maximum degree of , it follows by induction that is an integer polynomial in Since and and are both integer polynomials in , the theorem follows.
Proof of Theorem 1
To deduce Theorem 1 from the Fundamental Theorem of Symmetric Polynomials, fix a monic polynomial and note that the polynomial is symmetric in . By the Fundamental Theorem, there is a polynomial such that . Let Writing with , we have On the other hand, by (R3) and (R4) we have and Theorem 1 follows.
Dear Prof. Matt Baker san,
Thanks for your new proof on quadratic reciprocity. This is suprising for me as there is almost no number theoretic argument except the use of Euler’s criterion. Other than that, even Jacobi symbol did not appear.
I do have two questions:
– In the proof of proposition 1, the identify of the cofficients derived from the recurrence definition does not hold for n=5 and k=2, where left hand side equlas to 5 and right hand side equals to 13/2. I would guess the binomial of the second term of the right hand side may be binomial(n-1-k,k-1) instead of binomial(n-k,k).
– In the proof of the proposition 2, I guess the L_k(x^2) appeared in the identify of H_n(x) means a polynomil derived from L_k(x) by using the same coefficients and half the degree for all terms, as k is even so all terms of L_k(x) are even powered. I would define H_k(x^2)=L_k(x) for k even.
If my guess above is correct, then it is true that H_n+k(x)=H_n(x)*H_k(x)+(-1)^(k+1)*H_n-k(x), if n>k and one of n or k is even and the other is odd. However, which is odd and which is even is dependent. For instance, think of H_17(x) and H_3(x).
H_17(x)=H_14(x)*H_3(x)+(-1)^(3+1)*H_11(x)
In this example, n=14 and k=3, indicating it may not always the case that n is odd, k is even and n>k, which seems assumed in your proof of the proposition 2.
Note, however, as the above identity on H_n+k(x) still holds, I’d guess your argument is not affected at all.
Probably I may entirely misunderstood your proofs of propositions, if that is the case, please ignore my comments above.
Anyway, thanks for your wonderful new proof of quadratic reciprocity. I am writing Japanese articls in my blog which introduce your proof, with asistance use of Maxima CAS to play with Lucas polynomials and resultant computations. See https://maxima.hatenablog.jp .
Thanks and best regards,
Yasuaki Honda
Many thanks for your comments! You are exactly write on both counts and I’ve adjusted the proofs accordingly. Does it look correct now?
Yes! Thanks for incorporating my comments. Fixes in the article seem fine for me.
Dear Matt,
The proof you give of Euler’s criterion reminds me of Deligne’s proof on the order of a finite flat commutative group scheme, as explained in the paper by Oort-Tate, section 1, itself an elaboration of this computation : prod_x x = prod_x (ax) = a^n \prod_x x.
Similar results were classical when I was an undergrad, at least for a=-1, as well as an order 3 analogue using the permutation x -> 1-1/x of the projective line.
On the other hand, these resultants probably have, or should have, an elliptic analogue, replacing Gm by an elliptic curve (and the Lucas polynomials by the finite scheme corresponding to the x-coordinates of the torsion points, equivalently the image of torsion under quotient by ±1.)
Best,
Take care, Georgia’s on my mind these days,
Antoine