Tag Archives: Lucas polynomials

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.

Continue reading →