Prove that $p$ divides $F_{p-1}+F_{p+1}-1$

Question

Given the Fibonacci sequence $(F_n)$, defined by $F_0=0,F_1=1, F_{n+2}=F_{n+1}+F_n$, and $p$ an odd prime number, how to prove that $p$ divides $F_{p-1}+F_{p+1}-1$?

Is induction a good idea here?

Answer 1

We can notice that $$ F_{n-1}+F_{n+1} = L_n \tag{1}$$ holds by induction since equality holds for $n=1,2$ and both the LHS and the RHS satisfy the recurrence relation $f_{n+1}=f_{n}+f_{n-1}$. Given that, the problem boils down to proving that $$ L_p \equiv 1\pmod{p}.\tag{2}$$ Due to Binet's formula, this is trivial if $5$ is a quadratic residue $\!\!\pmod{p}$. In the other case, $$ \mathbb{F}_p[x]/(x^2-x-1)\simeq\mathbb{F}_{p^2}, \tag{3}$$ and the roots of $x^2-x-1$ are of the form $\xi,\xi^p$ by Frobenius' automorphism. On the other hand, $\xi+\xi^p=1$ by Viète's formulas, while $L_p=\xi+\xi^p$ by Binet's formula, hence $(2)$ holds also in that case.

Answer 2

Induction on primes is not going to be useful, because there isn't a simple relationship between one prime and the next. The Binet formula might be more useful. Note that there are two cases, depending on whether or not 5 is a square mod $p$ (if it isn't, you might want to work an extension field of the integers mod $p$).

Answer 3

There is an easier expression!

Let $G_n = F_{n+2} + F_{n} - 1$ be the sequence of numbers we are interested in. Note that $$ G_0 = F_2 + F_0 - 1 = 1 + 0 - 1 = 0\\ G_1 = F_3 + F_1 - 1 = 2 + 1 - 1 = 2 $$ and $$ G_{n+2} = F_{n+2} + F_{n} - 1 \\ = F_{n+1} + F_{n} + F_{n-1} + F_{n-2} - 1 \\ = G_{n+1} + G_{n} + 1 $$

[Edit: My derivation hereafter was in error. Removed]

Answer 4

Using

$$F_{n}=F_{n-2}+F_{n-1}$$ $$F_{2n}=F_{n}\left(2F_{n+1}-F_{n}\right)$$ $$F_{2n}=F_{n}L_{n}$$ where $L_{n}$ is the n-th Lucas number, we have$$F_{p-1}+F_{p+1}=F_{p-1}+F_{p}-F_{p}+F_{p+1}=2F_{p+1}-F_{p} =\frac{F_{2p}}{F_{p}}=L_{p}$$ and we have finished because, if $p$ is prime, holds $$L_{p}\equiv1\,\textrm{mod}\, p.$$