Quadratic reciprocity via generalized Fibonacci numbers?

This is a pet idea of mine which I thought I’d share. Fix a prime q congruent to 1mod4 and define a sequence Fn by F0=0,F1=1, and


Then Fn=αnβnαβ where α,β are the two roots of f(x)=x2xq14. When q=5 we recover the ordinary Fibonacci numbers. The discriminant of f(x) is q, so it splits modp if and only if q is a quadratic residue modp.

If (qp)=1, then the Frobenius morphism xxp swaps α and β (working over Fp), hence Fp1modp. And if (qp)=1, then the Frobenius morphism fixes α and β, hence Fp1modp. In other words,


Quadratic reciprocity in this case is equivalent to the statement that


Question: Does anyone have any ideas about how to prove this directly, thereby proving quadratic reciprocity in the case that q1mod4?

My pet approach is to think of Fp as counting the number of ways to tile a row of length p1 by tiles of size 1 and 2, where there is one type of tile of size 1 and q14 types of tiles of size 2. The problem is that I don’t see, say, an obvious action of the cyclic group Z/pZ on this set. Any ideas?


The following paper seems to answer your question: P. T. Young, “Quadratic reciprocity via Lucas sequences”, Fibonacci Quart. 33 (1995), no. 1, 78–81.

Here’s its MathSciNet Review by A. Grytczuk:

Let {γn}n=0 be a given Lucas sequence defined by γ0=0, γ1=1, γn+1=λγn+μγn1, n1, λ,μZ, and let q be an odd prime such that D=(1q)q=λ2+4μ. Then the author proves that there is a unique formal power series Φ with integer coefficients and constant term zero such that (1) n=1γnΦn(t)/n=n=1(nq)tn/n holds, where (nq) is the Legendre symbol.
From this result follows the Gauss law of quadratic reciprocity in the following form: (2) (pq)=(Dp), where p, q are distinct odd primes and D=(1q)q=λ2+4μ.

Here’s the direct link to the paper.

Source : Link , Question Author : Qiaochu Yuan , Answer Author : t.b.

Leave a Comment