Fibonacci Number with Prime Index 2n+1 is Congruent to 5^n Modulo p

Theorem

Let $p = 2 n + 1$ be an odd prime.

Then:

$F_p \equiv 5^n \pmod p$

$2^p F_p = 2 \ds \sum_{k \mathop \in \Z} \dbinom p {2 k + 1} 5^k$

$\forall k \in \Z: 0 < k < p: \dbinom p k \equiv 0 \pmod p$

$2^p \equiv 2 \pmod p$

Hence:

$\ds 2^p F_p$

$\equiv$

$\ds 2 F_p$

$\ds \pmod p$

$\ds \leadsto \ \ $

$\ds 2 \sum_{k \mathop \in \Z} \dbinom p {2 k + 1} 5^k$

$\equiv$

$\ds 2 \times 5^n$

as all $\dbinom p k \equiv 0 \pmod p$ except $\dbinom p p$

$\ds \leadsto \ \ $

$\ds 2^p F_p$

$\equiv$

$\ds 2 \times 5^n$

$\ds \pmod p$

$\ds \leadsto \ \ $

$\ds F_p$

$\equiv$

$\ds 5^n$

$\ds \pmod p$

because $p \perp 2$

$\blacksquare$