Is there a prime $p > 3$ such that the Fibonacci number $F_{np} \equiv -1 \mod p^2$ for some natural number $n$? I know none of the first $1000$ primes $> 3$ qualify.

EDIT: In response to Calvin Lin's comment: Suppose $n$ is the period mod $p$. Of course the period mod $p^2$ is a multiple of $n$. If $M = \pmatrix{1 & 1\cr 1 & 0\cr}$, so that $M^k = \pmatrix{F_{k+1} & F_k\cr F_k & F_{k-1}\cr}$, that says $M^n \equiv I \mod p$, so $M^n \equiv I + p A \mod p^2$ for some matrix $A$ with entries in $\mathbb Z_p$. Then $M^{kn} \equiv I + k p A \mod p^2$. If $A = 0$, the period mod $p^2$ is $n$, otherwise it is $pn$.

Note that $n$ divides $p-1$ (if $p \equiv \pm 4 \mod 5$) or $2p+2$ (if $p \equiv \pm 3 \mod 5$), and in either case is coprime to $p$. Thus if the period mod $p^2$ is not $pn$, $p$ must be a Fibonacci-Wieferich prime (see Noam Elkies' answer).


Solution 1:

The set of such primes $p$ is probably infinite but very sparse, and there are no such $p < 2 \cdot 10^{14}$.

We show that $p$ must be a "Fibonacci-Wieferich prime", i.e. a prime for which $F_k \equiv 0 \bmod p^2$ for some $k \not\equiv 0 \bmod p$; as with ordinary Wieferich primes (primes such as $1093$ and $3511$ for which $2^p \equiv 2 \bmod p^2$), the number of such $p \leq x$ is expected to grow as $\log \log x$ as $x \rightarrow \infty$. Conversely, any Fibonacci-Wieferich prime $p$ will admit a congruence $F_{np} \equiv -1 \bmod p^2$.

Suppose $p>5$. Recall that $F_m = (\varphi^m - \overline\varphi^m) / \sqrt{5}$, where $\varphi, \overline\varphi = (1 \pm \sqrt5) / 2$ with $\varphi \overline\varphi = -1$. Hence if $F_m \equiv -1 \bmod p^2$ then $\varphi^m \bmod p^2$ is a root of $X^2 + \sqrt5 \, X - (-1)^m = 0$. Thus if $m$ is odd then $$ \varphi^m = \frac{-1 \pm \sqrt{5}}{2} = -\varphi \ \ \text{or} \ \ \varphi^{-1}, $$ while if $m$ is even then $$ \varphi^m = \frac{-3 \pm \sqrt{5}}{2} = -\varphi^2 \ \ \text{or} \ \ -\!\varphi^{-2}. $$ [This even case is where we must assume $p \neq 3$, because the discriminant of $X^2 + \sqrt5 \, X - 1$ is $9 \equiv 0 \bmod 3$, so $\phi^m$ can be congruent to one of its roots only modulo 3 but still satisfy the quadratic equation modulo 9.] Thus if $m$ is odd then $\varphi^{m+1}$ or $-\varphi^{m-1}$ is $1 \bmod p^2$, while if $m$ is even then $-\varphi^{m+2}$ or $-\varphi^{m-2}$ is $1 \bmod p^2$. In each of these four cases, then, if $m=np$ then $\varphi^k \equiv 1 \bmod p^2$ for some $k$ that is not a multiple of $p$ (namely $k = m+1$, $2m-2$, or $2m\pm 4$). This makes $p$ a Fibonacci-Wieferich prime. The paper

Richard J. McIntosh and Eric L Roettger: A search for Fibonacci-Wieferich and Wolstenholme primes, Math. of Computation 76 #260 (2007), 2087-2094.

explains why we expect the $\log \log x$ behavior, and reports on an exhaustive search over $p < 2 \cdot 10^{14}$ that came up empty.

solutions $m$ of $F_m \equiv -1 \bmod p^2$ should include multiples of $p$.

Conversely, if $p$ is a Fibonacci-Wieferich prime then there exists some even $k \not\equiv 0 \bmod p$ such that $\varphi^k \equiv 1 \bmod p^2$. (If the smallest $k$ was odd then double it.) By "Chinese Remainder" $k$ has a multiple $k' \equiv 1 \bmod p$, and this $k'$ is again even with $\varphi^{k'} \equiv 1 \bmod p^2$. Therefore $F_{np} \equiv -1 \bmod p^2$ with $np = k'-1$ odd, QED.