TAOCP 1.2.8 Exercise 26
We start from Exercise 25, which asserts that 2^n F_n = 2 \sum_{\substack{k=1\\ k \text{ odd}}}^{\,n} \binom{n}{k} 5^{(k-1)/2}.
Section 1.2.8: Fibonacci Numbers
Exercise 26. [M20] Using the previous exercise, show that $F_p \equiv 5^{(p-1)/2}$ (modulo $p$) if $p$ is an odd prime.
Verified: no
Solve time: -
Solution
We start from Exercise 25, which asserts that
$$ 2^n F_n = 2 \sum_{\substack{k=1\ k \text{ odd}}}^{,n} \binom{n}{k} 5^{(k-1)/2}. \tag{25} $$
Let $p$ be an odd prime. We aim to show that
$$ F_p \equiv 5^{(p-1)/2} \pmod p. \tag{26} $$
From Eq. (25) with $n=p$, we have
$$ 2^p F_p = 2 \sum_{\substack{k=1\ k \text{ odd}}}^{,p} \binom{p}{k} 5^{(k-1)/2}. $$
We examine the sum modulo $p$. For $1 \le k \le p-1$, the binomial coefficient $\binom{p}{k}$ is divisible by $p$, because
$$ \binom{p}{k} = \frac{p!}{k!(p-k)!} = \frac{p \cdot (p-1)\cdots(p-k+1)}{k!} \equiv 0 \pmod p. $$
Therefore, modulo $p$ all terms with $1 < k < p$ vanish. The only surviving term corresponds to $k=p$, which is odd since $p$ is odd. Hence, modulo $p$, we obtain
$$ 2^p F_p \equiv 2 \cdot \binom{p}{p} 5^{(p-1)/2} = 2 \cdot 1 \cdot 5^{(p-1)/2} = 2 \cdot 5^{(p-1)/2} \pmod p. $$
Since $p$ is odd, Fermat's little theorem implies
$$ 2^p \equiv 2 \pmod p. $$
Dividing both sides of the congruence by $2$ (which is invertible modulo $p$ because $p \neq 2$), we find
$$ F_p \equiv 5^{(p-1)/2} \pmod p. $$
This completes the proof.
∎