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