TAOCP 1.2.8 Exercise 27
Let $p$ be a prime with $p \ne 5$.
Section 1.2.8: Fibonacci Numbers
Exercise 27. [M20] Using the previous exercise, show that if $p$ is a prime different from $5$, then either $F_{p-1}$ or $F_{p+1}$ (not both) is a multiple of $p$.
Verified: no
Solve time: -
Solution
Let $p$ be a prime with $p \ne 5$. By Exercise 1.2.8.26, we have
$$ F_p \equiv 5^{(p-1)/2} \pmod p. $$
By Euler's criterion, since $p \ne 5$,
$$ 5^{(p-1)/2} \equiv \begin{cases} 1 \pmod p & \text{if $5$ is a quadratic residue modulo $p$},\ -1 \pmod p & \text{if $5$ is a quadratic nonresidue modulo $p$}. \end{cases} $$
Therefore,
$$ F_p \equiv \pm 1 \pmod p. \tag{1} $$
Consider the identity from Section 1.2.8, equation (6), applied with $m = p-1$ and $n = 1$:
$$ F_{p} = F_{1} F_{p} + F_0 F_{p-1} = F_p + 0\cdot F_{p-1} = F_p, $$
which is trivial. More usefully, apply equation (6) with $m = p-1$ and $n = 2$:
$$ F_{p+1} = F_2 F_p + F_1 F_{p-1} = 1 \cdot F_p + 1 \cdot F_{p-1} = F_p + F_{p-1}. \tag{2} $$
Similarly, for $m = p+1$ and $n = 1$,
$$ F_{p+2} = F_1 F_{p+1} + F_0 F_p = F_{p+1}. $$
From equation (2), we can write
$$ F_{p+1} - F_{p-1} = F_p. $$
Reducing modulo $p$, we obtain
$$ F_{p+1} \equiv F_{p-1} + F_p \equiv F_{p-1} \pm 1 \pmod p, $$
where the sign is given by equation (1). In particular, exactly one of $F_{p-1}$ and $F_{p+1}$ is divisible by $p$, because $F_p \not\equiv 0 \pmod p$ (since $\pm 1 \ne 0 \pmod p$). If $F_p \equiv 1 \pmod p$, then $F_{p+1} \equiv F_{p-1} + 1 \pmod p$, so $F_{p+1} \not\equiv 0 \pmod p$ and $F_{p-1} \equiv -1 \pmod p \ne 0$; hence only $F_{p-1}$ or $F_{p+1}$ is divisible by $p$, depending on the residue of $5^{(p-1)/2}$. If $F_p \equiv -1 \pmod p$, a similar argument shows the other term is divisible by $p$.
Thus, exactly one of $F_{p-1}$ and $F_{p+1}$ is divisible by $p$. This completes the proof.
∎