Fibonacci pseudoprimes

If $p\equiv \pm 1 \pmod 5$ then $x^2-x-1$ factors as $(x-\phi)(x-\overline{\phi})$ in $\mathbb{F}_p$. Then your identities follow from $$F_n\equiv \frac{\phi^n-\overline{\phi}^n}{\phi - \overline{\phi}} \pmod p$$ since in this case $\phi^{p-1}\equiv 1$ (by Fermat) and $$\phi^{p+1}\equiv \phi^2 \equiv \phi+1$$ and likewise for $\overline{\phi}$.

If $p\equiv \pm 2 \pmod 5$ then the same polynomial factors in $\mathbb{F}_{p^2}$ and the Frobenius automorphism exchanges the roots. That is, $\phi^p=\overline{\phi}$ and $\overline{\phi}^p=\phi$. Your identities now follow from $$\phi^{p-1}\equiv \overline{\phi} \phi^{-1} \equiv -\overline{\phi}^2 \equiv -\overline{\phi}-1$$ and $$\phi^{p+1}\equiv \overline{\phi} \phi \equiv -1$$ and likewise for $\overline{\phi}$.