Prove Divisibility In Fibonacci Sequence Over A Prime Number

I'll prove the $1^\text{st}$ statement. Let $(\frac{a}{p})$ be the Legendre symbol of $a$ and $p$.

Theorem of Legendre and Lagrange. Let $p$ be an odd prime. Then

$$F_{p-1} \equiv \frac{1-(\frac{p}{5})}{2} \pmod p \quad \text{and} \quad F_{p+1} \equiv \frac{1+(\frac{p}{5})}{2} \pmod p.$$

Proof. You could find the theorem in this paper of Zhi-Hong Sun at page $4$ and the proof of the theorem at page $5$.

Directly from the theorem of Legendre and Lagrange we have that $F_{p-1} + F_{p+1} \equiv 1 \pmod p$ for every odd $p$ prime, which is equivalent to your first statement.

Here's a combinatorial proof. If $F_0=0$, $F_1=1$, then $F_{\ell+1}$ is the number of ways to tile a $1\times \ell$ strip with $1\times1$ squares and $1\times2$ rectangles. If the $1\times \ell$ strip is wrapped around a cylinder then the number of ways to tile the strip increases to $F_{\ell+1}+F_{\ell-1}$ because of configurations in which a $1\times 2$ rectangle spans the "seam" where the end of the strip meets the beginning. Note that we are still requiring that tile boundaries only occur with integer coordinates, rather than allowing them to vary continuously.

If $\ell$ is prime, then the only periodic configuration (with period less than $\ell$) is the one that consists entirely of $1\times1$ squares. Since no other configuration is equal to any of its $\ell$ cyclic shifts, $\ell$ divides $F_{\ell+1}+F_{\ell-1}-1$.

For general $\ell$, we can find the number of aperiodic tilings by Möbius inversion. Define $A_\ell$ to be the number of aperiodic tilings of the $1\times\ell$ strip with $1\times1$ squares and $1\times2$ rectangles. Since all cyclic shifts of aperiodic tilings are distinct from one another, $\ell$ divides $A_\ell$.

Now the total number of tilings is given by $$ F_{\ell+1}+F_{\ell-1}=\sum_{d\mid\ell}A_d. $$ By the Möbius inversion formula, $$ A_\ell=\sum_{d\mid\ell}\mu\left(\frac{\ell}{d}\right) \left(F_{d+1}+F_{d-1}\right), $$ where $\mu$ is the Möbius function.

Applying this to the case $\ell=p^{n+1}$, the divisors of $\ell$ are the powers $p^k$ with $k=0,1,\ldots,n+1$. Only $k=n$ and $k=n+1$ contribute to the sum since $$ \mu(\ell/d)=\mu(p^{n+1-k})=\begin{cases}0 & k<n\\ -1 & k=n\\ 1 & k=n+1. \end{cases} $$ Since $\ell$ divides $A_\ell$, the second statement now follows.

Remark I: In case elaboration is needed on any of the above points: when $\ell$ is prime, the set of tilings can be partitioned into one set of size $1$ and a bunch of sets of size $\ell$ as follows: define two tilings to be equivalent if they are cyclic shifts of each other. Then partition the set of tilings into equivalence classes. To see that the equivalence classes have size $1$ or $\ell$ when $\ell$ is prime, consider a tiling that is equal to one of its cyclic shifts. Let $s$ be the least such shift. It follows that the tiling is equal to the tiling shifted by $as+b\ell$ for arbitrary integers $a$, $b$. If $s$ does not divide $\ell$ then $\ell=qs+r$ with $0<r<s$ and the tiling is equal to the tiling shifted by $r=\ell-qs$, contradicting that $s$ is the least shift. Hence $s$ divides $\ell$ and, since $\ell$ is prime, $s$ equals $1$ or $\ell$. Furthermore, a tiling is equal to the tiling shifted by one unit if and only if it contains no $1\times 2$ tiles.

Möbius inversion is a way of expeditiously handling the case of general $\ell$, but for the prime-power case, a simple inclusion-exclusion suffices. If a tiling of length $\ell=p^{n+1}$ is periodic with period $t$, $t<p^{n+1}$, then $t\mid p^n$ and therefore the tiling is periodic with period $p^n$. Hence the set of aperiodic tilings of length $p^{n+1}$ is obtained by removing the tilings with period $p^n$ from the set of all tilings.

Remark II: Many sorts of tiling problems with cyclic symmetry are amenable to this method. A famous example: how many ways are there to tile a $1\times \ell$ strip wrapped on a cylinder with $1\times1$ squares of $a$ different colors? If $\ell$ is prime, then the only periodic tilings are those in which all $\ell$ tiles are of the same color. Hence $a^\ell-a$ is divisible by $\ell$ when $\ell$ is prime. This is Fermat's little theorem.