Fibonacci numbers modulo $p$

Solution 1:

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.

See also Theorem 4.12 of Niven, Zuckerman, and Montgomery.

Solution 2:

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.

Solution 3:

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.