Relationship between Primes and Fibonacci Sequence

Solution 1:

For primes $p > 5$, the Binet formula applies mod $p$, in the following sense. If $p \equiv \pm 1 \mod 5$, $5$ is a quadratic residue mod $p$, and $z^2 - z - 1$ has two roots $\phi_\pm = (1 \pm \sqrt{5})/2$ in ${\mathbb Z}_p$. Then $F_n \equiv ((\phi_+^n - \phi_-^n)/\sqrt{5} \mod p$. In particular, $F_{p-1}$ is divisible by $p$, so $\gcd(p, F_{p-1}) = p$.

If $p \equiv \pm 2 \mod 5$, $z^2 - z - 1$ doesn't have roots in ${\mathbb Z}_p$, but it has roots in an extension field $GF(p^2)$. In this case it turns out that $F_{p+1}$ is divisible by $p$, so $\gcd(p, F_{p+1}) = p$.

EDIT: Note that we have $\phi_+ + \phi_- = 1$ and $\phi_+ \phi_- = -1$. Since we're in characteristic $p$, $\phi_+^p + \phi_-^p = 1^p = 1$, and $\phi_+^p\phi_-^p = (-1)^p = -1$ as well. So $\phi_+^p$ and $\phi_-^p$ are also roots of $z^2 - z - 1$. But there are only two such roots. In the second case, we can't have $\phi_+^p = \phi_+$, because only elements of ${\mathbb Z}_p$ have the property $z^p = z$, so we must have $\phi_+^p = \phi_-$, and similarly $\phi_-^p = \phi_+$. Then $$F_{p+1} = \dfrac{\phi_+^{p+1} - \phi_-^{p+1}}{\sqrt{5}} = \dfrac{\phi_- \phi_+ - \phi_+ \phi_-}{\sqrt{5}} = 0 \ \text{(as a member of $GF(p^2)$)}$$ i.e. $F_{p+1} \equiv 0 \mod p$.