Prove that $p>5$ divides $(F_{p+1}-1)F_{p+1}$ 
Let the Fibonacci sequence be defined by $F_n = F_{n-1}+F_{n-2}$ where $F_1 = 1, F_2 = 1$. Prove that if $p > 5$ is a prime, then $p$ divides $(F_{p+1}-1)F_{p+1}$.

I thought about using some facts about the Fibonacci sequence such as that $F_n = \dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right)$, but I don't see how to use the fact that $n$ is prime.
 A: Indeed, we can use 
$$
F_n = \dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right).
$$
Let $p>5$ be a prime. We consider Fibonacci sequence in $\mathbb{F}_p$ or $\mathbb{F}_{p^2}$ depending on whether $(5|p)=1$ ($5$ is a quadratic residue mod $p$) or $(5|p)=-1$ ($5$ is a quadratic nonresidue mod $p$). 
If $(5|p)=1$, then every term in the expression of $F_n$ is well-defined over $\mathbb{F}_p$. By Fermat's little theorem ($a^p \equiv a \ \mathrm{mod} \ p$), we have
$$
F_{p+1} \equiv \frac 1{\sqrt 5} \left( \left( \frac{1+\sqrt 5}2\right)^2 - \left(\frac{1-\sqrt 5}2\right)^2\right)\equiv F_2 =1 \ \mathrm{mod} \ p.
$$
If $(5|p)=-1$, then $\sqrt 5$ is not well-defined in $\mathbb{F}_p$. We instead consider $\mathbb{F}_{p^2}$ obtained from adjoining $\sqrt 5$ to $\mathbb{F}_p$, say $\mathbb{F}_p(\sqrt 5)$. Let $\sigma$ be the Frobenious automorphism (maps $x$ to $x^p$, and fixes $\mathbb{F}_p$) of $\mathbb{F}_p(\sqrt 5)$. Since $\sigma$ is nontrivial on $\mathbb{F}_{p^2}$, we must have $\sigma(\sqrt 5)=-\sqrt 5$. To see this, consider  $(\sigma(\sqrt 5))^2 =\sigma((\sqrt 5)^2 ) = \sigma(5) = 5$. Thus, $\sigma(\sqrt 5)=\pm\sqrt 5$, but $\sigma(\sqrt 5)=\sqrt 5$ would give trivial automorphism. So, $\sigma(\sqrt 5)=-\sqrt 5$. Then over $\mathbb{F}_{p^2}$, we have
$$
F_{p+1}=\frac1{\sqrt 5} \left(  \frac{(1-\sqrt 5)(1+\sqrt 5)}4 - \frac{(1+\sqrt 5)(1-\sqrt 5)}4 \right)=0.
$$
This shows that $F_{p+1}$ is indeed $0$ in $\mathbb{F}_p$ as well. Thus, $F_{p+1}\equiv 0$ mod $p$. 
