Quadratic Reciprocity via Lucas Polynomials

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 L_0(x)=2, L_1(x)=x, and L_n(x)=xL_{n-1}(x)+L_{n-2}(x) for n \geq 2.

The next few terms in the sequence are L_2(x)=x^2+2, L_3(x)=x^3+3x, L_4(x)=x^4 + 4x^2 + 2, and L_5(x)=x^5+5x^3+5x.

By induction, the degree of L_n(x) is equal to n. The integers L_n(1) are the Lucas numbers, which are natural “companions” to the Fibonacci numbers (see, e.g., this blog post).

Edouard Lucas (source: Wikipedia)

The polynomials H_n(x)

It’s easy to see that for n odd, L_n(x) is divisible by x and L_n(x)/x has only even-power terms. Thus L_n(x)/x = H_n(x^2) for some monic integer polynomial H_n(x) of degree (n-1)/2. We will be particularly interested in the polynomials H_p(x) for p prime.

If n is even (resp. odd), a simple induction shows that the constant term (resp. the coefficient of x) in L_n(x) is equal to n. In particular, for n odd we have H_n(0)=n.


Given two monic polynomials f(x)=x^m+a_{m-1}x^{m-1} + \cdots + a_1x + a_0 = \prod_{i=1}^m (x - \alpha_i) and g(x) = x^n+b_{n-1}x^{n-1} + \cdots + b_1x + b_0 = \prod_{j=1}^n (x - \beta_j) with integer coefficients and roots \alpha_i, \beta_j \in {\mathbb C}, their resultant is defined to be {\rm Res}(f(x),g(x)) = \prod_{i,j} (\alpha_i - \beta_j).

The only nontrivial fact we will use about the resultant is the following:

Theorem 1: Given a monic polynomial f \in {\mathbb Z}[x] and a positive integer n, there is a polynomial S \in {\mathbb Z}[t_1,\ldots,t_n] such that {\rm Res}(f(x),g(x)) = S(b_{n-1},\ldots,\ldots,b_1,b_0) for every polynomial g(x) = x^n+b_{n-1}x^{n-1} + \cdots + b_1x + b_0 \in {\mathbb Z}[x].

The polynomial S 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 S 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 f(x) and g(x) belongs to {\mathbb Z}.

(R2) If h(x) is another monic polynomial of degree n and the coefficients of g(x) and h(x) are congruent modulo d (which we write as g(x) \equiv h(x) \pmod{d}) for some positive integer d, then {\rm Res}(f(x),g(x)) \equiv {\rm Res}(f(x),h(x)) \pmod{d}.

It is immediate from the definition that:

(R3) {\rm Res}(f(x),g(x)) = \prod_{i=1}^m g(\alpha_i).

(R4) {\rm Res}(f(x),g(x)) = (-1)^{mn}{\rm Res}(g(x),f(x)).

Two observations

Our proof of the Law of Quadratic Reciprocity will be based on the following two simple observations:

Proposition 1: For every prime p, we have L_p(x) \equiv x^p \pmod{p}. Equivalently, H_p(x) \equiv x^{(p-1)/2} \pmod{p}.

Proposition 2: If p,q are distinct odd primes then {\rm Res}(H_p(x),H_q(x)) = \pm 1.

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 p is prime and a is an integer not divisible by p, the Legendre symbol \left( \frac{a}{p} \right) is defined to be 1 if a is a quadratic residue mod p and -1 otherwise.

Theorem (Law of Quadratic Reciprocity): If p,q are distinct odd primes than \left( \frac{q}{p} \right) = (-1)^{(p-1)(q-1)/4} \left( \frac{p}{q} \right).

Proof: Let p,q be distinct odd primes. By Proposition 1, (R2), and (R3) we have {\rm Res}(H_p(x),H_q(x)) \equiv {\rm Res}(x^{(p-1)/2},H_q(x))=H_q(0)^{(p-1)/2} \pmod{p}. Since H_q(0)=q and q^{(p-1)/2} \equiv \left( \frac{q}{p} \right) \pmod{p} by Euler’s criterion, we have {\rm Res}(H_p(x),H_q(x)) \equiv \left( \frac{q}{p} \right) \pmod{p}. But {\rm Res}(H_p(x),H_q(x)) = \pm 1 by Proposition 2, so {\rm Res}(H_p(x),H_q(x)) = \left( \frac{q}{p} \right). By symmetry, we also have {\rm Res}(H_q(x),H_p(x)) = \left( \frac{p}{q} \right). So by (R4), \left( \frac{q}{p} \right) = (-1)^{(p-1)(q-1)/4} \left( \frac{p}{q} \right).

Proof of Proposition 1

We claim that for all n \geq 1,

(L1) L_n(x) = \sum_{k=0}^{\lfloor n/2 \rfloor} \frac{n}{n-k} \binom{n-k}{k} x^{n-2k}.

This easily implies Proposition 1. Since the claim holds for n=1 and n=2 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 \frac{n}{n-k} \binom{n-k}{k} = \frac{n-1}{n-k-1} \binom{n-k-1}{k} + \frac{n-2}{n-k-1} \binom{n-k-1}{k-1} for 0 \leq k \leq \lfloor n/2 \rfloor. But this is a straightforward algebraic exercise: just multiply both sides of the readily verified identity n(n-k-1) = (n-1)(n-2k) + (n-2)k by \frac{(n-k-2)!}{k! (n-2k)!}.

Further properties of Lucas polynomials and resultants

Our proof of Proposition 2 will make use of the following formulas:

(L2) L_n = \alpha^n + \beta^n for all n \geq 0, where \alpha = (x + \sqrt{x^2+4})/2 and \beta = (x - \sqrt{x^2+4})/2.

(This is a generalization of the Binet formula L_n(1) = \phi^n + {\bar\phi}^{n} for the Lucas numbers, where \phi is the golden ratio.)

(L3) L_{m+n}(x)=L_m(x)L_n(x) + (-1)^{n+1} L_{m-n}(x) for all m \geq n.

(This also generalizes a well-known property of Lucas numbers.)

(R5) If f(x) = q(x) g(x) + r(x) with f(x),g(x),q(x),r(x) monic integer polynomials then {\rm Res}(g(x),f(x)) = {\rm Res}(g(x),r(x)).

To prove (L2), it suffices to note that \alpha^2 = x\alpha + 1 and therefore \alpha^n = x\alpha^{n-1} + \alpha^{n-2} for all n \geq 2, and similarly for \beta. Since (L2) holds for n=0 and n=1 by inspection, the identify follows for all n \geq 0 by induction.

To prove (L3), note that \alpha^{m+n} + \beta^{m+n} = (\alpha^m + \beta^m)(\alpha^n + \beta^n) - (\alpha\beta)^n (\alpha^{m-n} + \beta^{m-n}). Since \alpha\beta = -1, (L3) follows from (L2).

To prove (R5), note from (R3) that {\rm Res}(g(x),r(x)) = \prod_{j=1}^n r(\beta_j) = \prod_{j=1}^n f(\beta_j) = {\rm Res}(g(x),f(x)) since f(\beta_j) = q(\beta_j)g(\beta_j) + r(\beta_j) and g(\beta_j)=0 for all j.

Proof of Proposition 2

Note first that (L3) implies that when n is odd and k < n is even we have

H_{n+k}(x)=H_n(x)L_k(x^2) + (-1)^{k+1} H_{n-k},

and similarly when n is odd and k > n is even we have

H_{n+k}(x)=H_n(x)L_k(x^2) + (-1)^{n+1} H_{k-n}.

We claim that if m,n are odd positive integers with n < m and {\rm GCD}(m,n)=1 then {\rm Res}(H_m(x),H_n(x))= \pm 1. We will show this by induction on n. For n = 1 we have H_n(x)=1 and the result is clear. For the inductive step, write m = n + k with k even and note that from (R5),

{\rm Res}(H_n,H_m) = {\rm Res}(H_n,H_n(x)L_k(x^2) \pm H_{|n-k|}) = {\rm Res}(H_n, \pm H_{|n-k|}) = \pm {\rm Res}(H_n,H_{|n-k|}).

Furthermore, {\rm GCD}(n,|n-k|)=1 since any common divisor of n and n-k will also divide k and hence m=n+k. By induction, {\rm Res}(H_n,H_{|n-k|}) = \pm 1 and the claim follows.

This completes our proof of the Law of Quadratic Reciprocity.

Relation to other proofs

The zeros of L_n(x) are x = 2i \cos \frac{(2k+1)\pi}{2n} for k=0,1,\ldots,n-1 (see this paper for a proof). Using this, one can show that when p is prime, H_p(x+2) is the minimal polynomial of \zeta_p + \zeta_p^{-1}, where \zeta_p \in {\mathbb C} is a primitive p^{\rm th} root of unity. (Note that Proposition 1 and the fact that H_p(0)=p show that H_p(x) 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 H_p(x+2) in our proof equal to T_p(x) 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 T_p(x+1/x) x^{(p-1)/2} = \Phi_p(x), 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 g(x) = x^p - 2 (which is congruent to (x-2)^p modulo p), 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 m,n are odd positive integers with n < m and {\rm GCD}(m,n)=1 then {\rm Res}(H_m(x),H_n(x))= \pm 1. Conversely, if {\rm GCD}(m,n) \neq 1 one can show (using the fact that L_n(x) forms an odd divisibility sequence, as mentioned here) that {\rm Res}(H_m(x),H_n(x))= 0.

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 p. 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 p is an odd prime and a is a non-zero quadratic residue modulo p then there are precisely 2 solutions (modulo p) to x^2 \equiv a \pmod{p}.

Proof: Since a is a quadratic residue, there exists b such that b^2 \equiv a \pmod{p}. The congruence x^2 \equiv a \pmod{p} is equivalent to p \mid (x-b)(x+b), which implies that p \mid b or p \mid -b. Thus x \equiv b or x \equiv -b \pmod{p}. Since p>2 and a \not\equiv 0 \pmod{p}, we have b \not\equiv 0 \pmod{p} as well and thus b \not\equiv -b \pmod{p}.

Theorem (Euler’s Criterion): If p is an odd prime and a is an integer not divisible by p, then a^{(p-1)/2} is congruent to 1 modulo p if a is a quadratic residue mod p and to -1 \pmod{p} if a is not a quadratic residue mod p.

Proof: Let {\mathbb F}_p^* denote the set \{ 1,2,\ldots,p-1 \} modulo p, and let m = (p-1)/2. By the lemma, there are precisely m quadratic residues and m non-residues modulo p, since the map {\mathbb F}_p^* \to {\mathbb F}_p^* given by x \mapsto x^2 \pmod{p} is 2-to-1 and its image is precisely the set of quadratic residues mod p.

Given a \in {\mathbb F}_p^*, define \psi_a : {\mathbb F}_p^* \to {\mathbb F}_p^* by \psi_a(x) \equiv ax^{-1} \pmod{p}. Then x \psi_a(x) \equiv a \pmod{p} for all x and \psi_a is an involution, i.e., \psi_a(x)=y iff \psi_a(y)=x. Note that \psi_a(x) \equiv x \pmod{p} iff x^2 \equiv a \pmod{p}.

If a is not a quadratic residue, we have x \not\equiv \psi_a(x) for all x. In this case, pairing x to y=\psi_a(x) gives a grouping of all elements of {\mathbb F}_p^* into m distinct pairs, with the elements of each pair multiplying to a modulo p. Thus 1 \cdot 2 \cdots (p-1) \equiv a^m \pmod{p}.

If a is a quadratic residue, the grouping works in the same way except that there are (by the Lemma) precisely two pairs \{ x, y=\psi_a(x) \} with x=y, namely the two square roots \pm b of a modulo p. Since b \cdot -b \equiv -a \pmod{p}, we have 1 \cdot 2 \cdots (p-1) \equiv -a \cdot a^{m-1} \pmod{p}.

In terms of the Legendre symbol, this gives (p-1)! \equiv -\left( \frac{a}{p} \right) a^{(p-1)/2} \pmod{p} for all a. Setting a=1 shows that (p-1)! \equiv -1 \pmod{p} (Wilson’s theorem), and thus \left( \frac{a}{p} \right) \equiv a^{(p-1)/2} \pmod{p} for all a \in {\mathbb F}_p^* (Euler’s criterion).

As a bonus, squaring both sides in Euler’s criterion gives a^{p-1} \equiv 1 \pmod{p} (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 p(x_1,\ldots,x_n) \in {\mathbb Z}[x_1,\ldots,x_n] is invariant under all permutations of the variables x_1,\ldots,x_n, then there is a polynomial q(t_1,\ldots,t_n) \in {\mathbb Z}[t_1,\ldots,t_n] such that p(x_1,\ldots,x_n) = q(e_1,\ldots,e_n), where e_1,\ldots,e_n are the elementary symmetric polynomials in x_1,\ldots,x_n.

Proof: Let d_i be the degree of p as a polynomial in x_i. The proof is by induction on d := {\rm max}(d_1,\ldots,d_n) and the number of variables n. If d=0 or n=1 the result is trivial. Now assume the result is true for polynomials of degree smaller than d and for polynomials in fewer than n variables, and define \tilde{p} \in {\mathbb Z}[x_1,\ldots,x_{n-1}] by \tilde{p}(x_1,\ldots,x_{n-1}) = p(x_1,\ldots,x_{n-1},0). Then \tilde{p} is invariant under permuting x_1,\ldots,x_{n-1}, so by induction there is an integer polynomial q_1 in n-1 variables such that \tilde{p}(x_1,\ldots,x_{n-1}) = q_1(e_1(x_1,\ldots,x_{n-1}),\ldots,e_{n-1}(x_1,\ldots,x_{n-1})).

Let q_2 := q_1(e_1(x_1,\ldots,x_n),\ldots,e_{n-1}(x_1,\ldots,x_n)) be the corresponding polynomial in the symmetric functions e_1,\ldots,e_{n-1} of one additional variable. Then p(x_1,\ldots,x_{n-1},0) - q_2(x_1,\ldots,x_{n-1},0) = 0, so q_3(x_1,\ldots,x_{n-1},x_n) := p(x_1,\ldots,x_{n-1},x_n) - q_2(x_1,\ldots,x_{n-1},x_n), considered as a polynomial in x_n with coefficients in {\mathbb Z}[x_1,\ldots,x_{n-1}], has a zero at x_n=0, and thus x_n divides q_3. Since p and q_2 are both symmetric in x_1,\ldots,x_n, so is q_3, and therefore x_1,\ldots,x_{n-1} divide q_3 as well. So q_3(x_1,\ldots,x_n) is divisible by the product x_1 \cdots x_n.

Define q_4(x_1,\ldots,x_n) := q_3(x_1,\ldots,x_n)/(x_1\cdots x_n). Since either q_3 = 0 or the maximum degree of q_4 is strictly less than the maximum degree of q, it follows by induction that q_4 is an integer polynomial in e_1(x_1,\ldots,x_n),\ldots,e_n(x_1,\ldots,x_n). Since p = q_2 + q_3 = q_2(x_1,\ldots,x_n) + e_n(x_1,\ldots,x_n) q_4(x_1,\ldots,x_n) and q_2 and q_4 are both integer polynomials in e_1(x_1,\ldots,x_n),\ldots,e_n(x_1,\ldots,x_n), the theorem follows.

Proof of Theorem 1

To deduce Theorem 1 from the Fundamental Theorem of Symmetric Polynomials, fix a monic polynomial f(x) \in {\mathbb Z}[x] and note that the polynomial R(x_1,\ldots,x_n) = \prod_{j=1}^n f(x_j) is symmetric in x_1,\ldots,x_n. By the Fundamental Theorem, there is a polynomial \tilde{S}(t_1,\ldots,t_n) \in {\mathbb Z}[t_1,\ldots,t_n] such that R(x_1,\ldots,x_n) = \tilde{S}(e_1(x_1,\ldots,x_n),\ldots,e_n(x_1,\ldots,x_n)). Let S(t_1,\ldots,t_n) = (-1)^{mn} \tilde{S}(-t_1,t_2,-t_3,\ldots,(-1)^n t_n). Writing g(x) = x^n+b_{n-1}x^{n-1} + \cdots + b_1x + b_0 = \prod_{j=1}^n (x - \beta_j) with \beta_j \in {\mathbb C}, we have (-1)^{mn} R(\beta_1,\ldots,\beta_n) = S(b_{n-1},\ldots,b_1,b_0). On the other hand, by (R3) and (R4) we have {\rm Res}(f(x),g(x)) = (-1)^{mn} \prod_{j=1}^n f(\beta_j) = (-1)^{mn} R(\beta_1,\ldots,\beta_n), and Theorem 1 follows.

4 thoughts on “Quadratic Reciprocity via Lucas Polynomials

  1. 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).
    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

  2. 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.)
    Take care, Georgia’s on my mind these days,


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s