Number Theory – Quadratic Reciprocity via Generalized Fibonacci Numbers

Question

This is a pet idea of mine which I thought I'd share. Fix a prime $q$ congruent to $1 \bmod 4$ and define a sequence $F_n$ by $F_0 = 0, F_1 = 1$, and

$\displaystyle F_{n+2} = F_{n+1} + \frac{q-1}{4} F_n.$

Then $F_n = \frac{\alpha^n – \beta^n}{\alpha – \beta}$ where $\alpha, \beta$ are the two roots of $f(x) = x^2 – x – \frac{q-1}{4}$. When $q = 5$ we recover the ordinary Fibonacci numbers. The discriminant of $f(x)$ is $q$, so it splits $\bmod p$ if and only if $q$ is a quadratic residue $\bmod p$.

If $\left( \frac{q}{p} \right) = -1$, then the Frobenius morphism $x \mapsto x^p$ swaps $\alpha$ and $\beta$ (working over $\mathbb{F}_p$), hence $F_p \equiv -1 \bmod p$. And if $\left( \frac{q}{p} \right) = 1$, then the Frobenius morphism fixes $\alpha$ and $\beta$, hence $F_p \equiv 1 \bmod p$. In other words,

$\displaystyle F_p \equiv \left( \frac{q}{p} \right) \bmod p.$

Quadratic reciprocity in this case is equivalent to the statement that

$\displaystyle F_p \equiv \left( \frac{p}{q} \right) \bmod p.$

Question: Does anyone have any ideas about how to prove this directly, thereby proving quadratic reciprocity in the case that $q \equiv 1 \bmod 4$?

My pet approach is to think of $F_p$ 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 $\frac{q-1}{4}$ types of tiles of size $2$. The problem is that I don't see, say, an obvious action of the cyclic group $\mathbb{Z}/p\mathbb{Z}$ on this set. Any ideas?

Answer 1

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 $\{\gamma_n\}^\infty_{n=0}$ be a given Lucas sequence defined by $\gamma_0=0$, $\gamma_1=1$, $\gamma_{n+1}=\lambda \gamma_n+\mu \gamma_{n-1}$, $n\geq 1$, $\lambda, \mu\in{\bf Z}$, and let $q$ be an odd prime such that $D=(\frac{-1}q)q=\lambda^2+4\mu$. Then the author proves that there is a unique formal power series $\Phi$ with integer coefficients and constant term zero such that (1) $\sum^\infty_{n=1}\gamma_n\Phi^n(t)/n=\sum^\infty_{n=1}(\frac nq)t^n/n$ holds, where $(\frac nq)$ is the Legendre symbol.
From this result follows the Gauss law of quadratic reciprocity in the following form: (2) $(\frac pq)=(\frac Dp)$, where $p$, $q$ are distinct odd primes and $D=(\frac{-1}q) q=\lambda^2+4\mu$.

Here's the direct link to the paper.