Proof of an unknown source Fibonacci identity with double modulo

Question

Many years ago, I saw the following Fibonacci identity from somewhere online, without proof:

Let usual $F(n)$ be Fibonacci numbers with $F(0) = 0, F(1) = 1$, then we have

$$F(n) = \left(p ^ {n + 1} \bmod \left(p ^ 2 - p - 1\right)\right) \bmod p$$

where $p = 2 ^ {n + 1}$.

I couldn't find the source anymore, and it wouldn't help anyway as it didn't contain a proof. As far as I looked around Google search results this is not documented anywhere notable (e.g Wikipedia or here); Fibonacci identities with modulo are usually discussed under the topic of Pisano period, and never contains 2 modulo. However, it looks like it has something to do with the generating function.

Is there a proof for this identity, or are there any existing material where this identity is mentioned/proved?

Edit

There is a write-up on a very similar identity here, proven using generating function:

$$ F(n) = \left\lfloor\frac{p ^ {n + 1}} {p ^ 2 - p - 1}\right\rfloor \bmod p $$

They look almost the same but can't be more different! One is the quotient and one is the modulo. I'm not even sure if they are related to each other.

Answer 1

If you consider the inner expression in $\mathbb{Z}/(p^2-p-1)$, $$p^{n+1} \bmod (p^2 - p - 1) = F(n+1)p + F(n)$$ Proof by induction: with $n=0$ we have $p \bmod (p^2 - p - 1) = p = F(1)p + F(0)$. Then for the inductive step, \begin{eqnarray*}{(F(n+1)p + F(n))p} &=& {F(n+1)p^2 + F(n)p} \\ &=& {F(n+1)(p+1) + F(n)p} \\ &=& {F(n+2)p + F(n+1)}\end{eqnarray*}

Thus the identity $F(n) = (p^{n+1} \bmod (p ^ 2 - p - 1)) \bmod p$ holds for any $p > F(n)$.