Fibonacci Numbers and Legendre symbol

Below is an approach through algebraic number theory, which I hope is acceptable.
Let $\varphi=\frac{1+\sqrt5}{2}.$ Then $F_n=\frac{\varphi^n-\overline\varphi^n}{\varphi-\overline\varphi}\in\mathcal O:=\mathbb Z[\frac{1+\sqrt5}{2}].$ And we may study the divisibility of $F_n$ in $\mathcal O,$ as the divisibility of two rational integers in $\mathcal O$ is equivalent with the divisibility in $\mathbb Z$.
The case $p=5$ is either checked by $F_5\equiv(\varphi-\overline\varphi)^4\pmod5$ or by direct computation: $F_5=5.$ Also, the case $p=2$ is easily checked by $F_3=2.$
So in the following we suppose that $p$ is a prime different from $2$ and $5.$

Lemma I. $F_p\equiv\left(\dfrac{5}{p}\right)\pmod p.$
Indeed, $F_p\equiv(\varphi-\overline\varphi)^{p-1},$ as $(x-y)^p\equiv(x^p-y^p)\pmod p$ as polynomials. So $F_p\equiv(\sqrt5)^{p-1}=5^{\frac{p-1}{2}}\equiv\left(\dfrac{5}{p}\right)\pmod p$
$\square$

Lemma II. $\varphi\equiv\frac{p+1}{2}(1+\sqrt5)\pmod p.$
Notice that if $x$ is a solution to $2x\equiv(1+\sqrt5)\pmod p,$ then, multiplying both sides by $\frac{p+1}{2},$ we find $x\equiv\frac{p+1}{2}(1+\sqrt5)\pmod p.$ Then the result follows as $\varphi$ is a solution to the above equation.
$\square$

Lemma III. $\overline\varphi^p\equiv(\frac{p+1}{2})^p(1-\sqrt5)^p\equiv(\frac{p+1}{2})(1-(\sqrt5)^{p-1}\sqrt5)=\begin{cases} \varphi&\text{ if }\left(\dfrac{5}{p}\right)=-1\\\overline{\varphi}&\text{ if } \left(\dfrac{5}{p}\right)=1\end{cases}\pmod p.$
The statement itself can be counted as a proof as well.
$\square$

Two more observations: $$\begin{cases}F_{p+1}=\varphi F_p+\overline\varphi^p\\F_{p-1}=\varphi^{-1}F_p-\overline\varphi^p(\frac{\overline\varphi^{-1}-\varphi^{-1}}{\varphi-\overline\varphi})=\varphi^{-1}F_p+\overline\varphi^p\end{cases}.$$ These are easily check by writing out the expressions on both sides.
Finally, we see that, if $\left(\dfrac{5}{p}\right)=1,$ then $F_{p-1}\equiv\varphi^{-1}+\overline{\varphi}=-\overline\varphi+\overline\varphi=0\pmod p,$ while, if $\left(\dfrac{5}{p}\right)=-1,$ then $F_{p+1}\equiv -\varphi+\varphi=0\pmod p.$ Q.E.D.

If there are any errors or inappropriate points, or if you don't understand something, please tell me so that I can improve upon this answer, thanks in advance.
P.S. (In the above discussion the prime $2$ is excluded as there is no $2^{-1}$ in this case, but the case $p=2$ is easily checked.)

Let $x=(1+\sqrt 5)/2$ and $y=(1-\sqrt 5)/2$. Let $p$ be prime with $2\ne p\ne 5$.Let $q=(p-1)/2.$ We have $F(p)=(x^p-y^p)/\sqrt 5.$

Modulo $p$ we have $$2 F(p)\equiv 2^p F(p)\equiv [(1+\sqrt 5)^p-(1-\sqrt 5)^p]/\sqrt 5.$$ Expanding each of $(1\pm \sqrt 5)$ by the binomial theorem, and using the fact that $$\binom {p}{j}\equiv 0 \pmod p$$ when $1\leq j\leq p-1,$ we obtain $$2 F(p)\equiv 2 \cdot 5^q \pmod p.$$ Now apply the same method to find $2^{p+1}F(p+1)$, which is congruent to $4F(p+1)$ modulo $p$, using the fact that $$\binom {p+1}{j}=\binom {p}{j}+\binom {p}{j-1} \equiv 0 \pmod p$$ when $2\leq j\leq p-1,$ and $\binom {p+1}{1}=\binom {p+1}{p}=p+1\equiv 1 \pmod p.$

$$\text {We obtain }\quad 4 F(p+1)\equiv 2(1+5^q)\pmod p.$$

Therefore $F(p+1)\equiv 0\pmod p$ when $5$ is not a square mod $p$.

And when $5$ is a square mod $p$ we have $F(p+1)\equiv F(p)\equiv 1\pmod p$, so $F(p-1)=F(p+1)-F(p)\equiv 0\pmod p.$