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

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$.

Resultants

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.

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. Yasuaki Honda says:

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?

2. Yasuaki Honda says:

Yes! Thanks for incorporating my comments. Fixes in the article seem fine for me.