Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
@Q.Yuan: Hi did you look at this paper, this may contain what you need. projecteuclid.org/… –  anonymous Aug 14 '10 at 21:02
@Chandru1: the paper doesn't seem to be relevant. –  Qiaochu Yuan Aug 14 '10 at 21:48
do you have a path interpretation for F_n (like the one we now for q=5)? (maybe it would be easier to find Z/p-action there) –  Grigory M Aug 14 '10 at 22:37
Yes; it comes from the tiling interpretation. F_n counts paths on the graph with adjacency matrix [[1 1][(q-1)/4 0]]. –  Qiaochu Yuan Aug 15 '10 at 3:40
@Qiaochu Yuan: well, of course, but this one doesn't seem to be the "right" path interpretation, since it doesn't give the path graph of length 4 for q=5 (motivation: I don't like strange number (q-1)/4 — a path of length q-1 looks much better) –  Grigory M Aug 15 '10 at 11:03

1 Answer 1

up vote 21 down vote accepted

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.

share|improve this answer
Glanced at the paper. It's not quite as direct as I would've liked, since it uses Gauss sums, but there is an interesting connection with formal group laws towards the end. –  Qiaochu Yuan Jan 8 '11 at 14:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.