# Fibonacci numbers modulo $p$

If $p$ is prime, then $F_{p-\left(\frac{p}{5}\right)}\equiv 0\bmod p$, where $F_j$ is the $j$th Fibonacci number, and $\left(\frac{p}{5}\right)$ is the Jacobi symbol.

Who first proved this? Is there a proof simple enough for an undergraduate number theory course? (We will get to quadratic reciprocity by the end of the term.)

• I really like the book 'A primer of analytic number theory'. The chapter on getting the class number using integration was quite nice! Feb 23 '12 at 5:43

I recommend Chapter XVII of Volume 1 of Dickson's History of the Theory of Numbers. He cites results of Legendre, Gauss, Dirichlet, and Lagrange, among others, none of them exactly the one you cite, but all of them very closely related, and more general.

Hardy and Wright give two proofs. It's Theorem 180 in the chapter on continued fractions, and then there's another proof at the end of section 4 of Chapter 15, Quadratic Fields.

The Pell conic $\mathcal{C} : x^2 - 5 y^2 = 4$ has $p - (5/p)$ points modulo $p$. The polynomials $$f_{-1} = x, f_0 = 2, f_n = x f_{n-1} - f_{n-2}$$ $$g_{-1} = -1, g_0 = 0, g_n = x g_{n-1} - g_{n-2}$$ perform multiplication by $n$ in the group $\mathcal{C}(\mathbb{F}_p)$, $n (x, y) = (f_n(x), y \cdot g_n(x))$. Let $P = (3, 1) \in \mathcal{C}(\mathbb{F}_p)$. Observe that $g_n(3)$ is the $n+2$-th Fibonacci number. It follows that $$(p - (5/p))P \equiv (2, 0) \pmod{p}$$ since $(2,0)$ is the identity element.

• This is very cool! Feb 24 '12 at 17:17
• Thanks! It looks like reciprocity might be needed since we get $p-(5/p)$ instead of $p-(p/5)$. Maybe you get another proof of reciprocity by computing $F_{p-(5/p)}$ a different way? Victor Scharaschkin and I used Pell conics and p-torsion in Rocky Mountain J. 2012, but that was different. Feb 25 '12 at 0:01

Here's a proof that only uses a little Galois theory of finite fields (and QR). I don't know if it's any of the proofs referenced by Gerry. Recall that $$F_n = \frac{\phi^n - \varphi^n}{\phi - \varphi}$$

where $\phi, \varphi$ are the two roots of $x^2 = x + 1$. Crucially, this formula remains valid over $\mathbb{F}_{p^2}$ where $p$ is any prime such that $x^2 = x + 1$ has distinct roots, thus any prime not equal to $5$. We distinguish two cases:

• $x^2 = x + 1$ is irreducible. This is true for $p = 2$ and for $p > 2, p \neq 5$ it's true if and only if the discriminant $\sqrt{5}$ isn't a square $\bmod p$, hence if and only if $\left( \frac{5}{p} \right) = -1$, hence by QR if and only if $\left( \frac{p}{5} \right) = -1$. In this case $x^2 = x + 1$ splits over $\mathbb{F}_{p^2}$ and the Frobenius map $x \mapsto x^p$ generates its Galois group, hence $\phi^p \equiv \varphi \bmod p$. It follows that $\phi^{p+1} \equiv \phi \varphi \equiv -1 \bmod p$ and the same is true for $\varphi$, hence that $F_{p+1} \equiv 0 \bmod p$.

• $x^2 = x + 1$ is reducible. This is false for $p = 2$ and for $p > 2, p \neq 5$ it's true if and only if $\left( \frac{p}{5} \right) = 1$. In this case $x^2 = x + 1$ splits over $\mathbb{F}_p$, hence $\phi^{p-1} \equiv 1 \bmod p$ and the same is true for $\varphi$, hence $F_{p-1} \equiv 0 \bmod p$.

The case $p = 5$ can be handled separately. Maybe this is slightly ugly, though.

• The claim for a single prime $p$ can be shown in a completely elementary way using the fact that the Fibonacci sequence $\bmod p$ is periodic. In particular, if $p=5$ the sequence $\bmod 5$ starts out $0$,$1$, $1$, $2$, $3$, $\overline{F}_5=0$ and inductively if $\overline{F}_{5k}=0$ then the next terms are $x$, $x$, $2x$, $3x$, $\overline{F}_{5(k+1)}=5x=0$. Feb 23 '12 at 8:26
• @Andrea: by "maybe this is slightly ugly" I just mean that maybe the use of casework is slightly ugly (for example relative to Samuel Hambleton's answer which nicely avoids it). Feb 23 '12 at 8:33