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

Fn+2=Fn+1+q−14Fn.

Then Fn=αn−βnα−β where α,β are the two roots of f(x)=x2−x−q−14. 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 x↦xp swaps α and β (working over Fp), hence Fp≡−1modp. And if (qp)=1, then the Frobenius morphism fixes α and β, hence Fp≡1modp. In other words,

Fp≡(qp)modp.

Quadratic reciprocity in this case is equivalent to the statement that

Fp≡(pq)modp.

Question:Does anyone have any ideas about how to prove this directly, thereby proving quadratic reciprocity in the case that q≡1mod4?My pet approach is to think of Fp as counting the number of ways to tile a row of length p−1 by tiles of size 1 and 2, where there is one type of tile of size 1 and q−14 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?

**Answer**

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+μγn−1, n≥1, λ,μ∈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.

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