# Fibonacci $\equiv -1 \mod p^2$

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).

• How are you indexing your Fibonacci numbers? $F_0 = 0, F_1 = 1$? – Arthur Jul 18 '15 at 0:01
• So $F_6 = 8 \equiv -1 \pmod 9?$ – Will Jagy Jul 18 '15 at 0:06
• @WillJagy Other than p > 3, it satisfies the conditions – Calvin Lin Jul 18 '15 at 0:08
• @CalvinLin, I'm just confirming the numbering, the reason for requiring $p>3$ and so on. Sometimes I do monster computer runs on these problems, I like to be sure what I am looking at. – Will Jagy Jul 18 '15 at 0:11
• It will probably will become famous Israel's conjecture in the future! – L.G. Jul 21 '15 at 6:45

## 2 Answers

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.

• I don't get how you deduce that $\varphi^m$ has to be a root of $X^2 + \sqrt 5 X + (-1)^m$ – mercio Jul 22 '15 at 8:02
• Sorry, I switched even and odd $m$; I'll fix it next. The argument is: $\varphi^m - \varphi^{-m} = -\sqrt 5$, and $\varphi^m \cdot \varphi^{-m} = (-1)^m$, so $X = \varphi^m$ satisfies $X - (-1)^m/X = -\sqrt 5$, whence $X^2 +\sqrt 5 - (-1)^m = 0$. – Noam D. Elkies Jul 22 '15 at 8:18
• Happily the corrected version also makes the Fibonacci-Wieferich condition sufficient as well as necessary. – Noam D. Elkies Jul 22 '15 at 8:28
• [typo in my first comment: the final equation is $X^2 +\sqrt 5 \, X - (-1)^m = 0$ as earlier, not $X^2 +\sqrt 5 - (-1)^m = 0$.] – Noam D. Elkies Jul 22 '15 at 14:55
• alright, also it's just $(X-\phi^m)(X+\overline{\phi}^m)$ and that threw me off. Also, I think you have a few wrong signs in the following two lines, at least the $\pm$ should be in fron of $1$ and $3$ and not $\sqrt 5$, but it shouldn't break everything. – mercio Jul 22 '15 at 15:46

Let $F_{u_{p^1}}$, denote the least positive Fibonacci number divisible by the prime $p$.

Let $F_{u_{p^2}}$, denote the least positive Fibonacci number divisible by $p^2$.

Let $\prod_{1}^{n\ge 1}$ be a quotient of primitive(characteristic) prime factor(s), ie factors that have not occurred in any earlier Fibonacci numbers. This may be represented below as an empty product of one, if the quotient divides $F_{p^{e}_{1}},\ e>1$.

$\left \lbrace {n \mid m}\ \text{iff}\ {F_n \mid F_m} \right \rbrace\, n \ge 3$ David Wells 1986, p.65

$p^2 \mid F_{u_{p^1}}\ \text{iff}\ F_{p^2} \mid F_{F_{u_{p^1}}}$

If an integer $i$, has prime factorization, $p_{1}^{e_{1}}\cdot\ p_{2}^{e_{2}}...p_{n}^{e_{n}}$ then the entry point of $i$ equals, $\left \lbrace u_{i} = \operatorname{lcm}[{ u_{p_{1}^{e_{1}}}, u_{p_{2}^{e_{2}}}, ...u_{p_{n}^{e_{n}}}}] \right \rbrace$.Marc Renault 1996 p.19 theorem 3.3 http//webspace.ship.edu/msrenault/fibonacci/FibThesis.pdf

$\text{If}\ i=F_{F_{u_{p^1}}}\ \text{then, }\ F_{p^2} \nmid\! F_{F_{u_{p^1}}}\text{ because } \left \lbrace u_{(F_{F_{u_{p^1}}})}\neq u_{(F_{F_{u_{p^2}}})} \right \rbrace$.

An abstract example of a Fibonacci-Wieferich prime p, where $p_{1}=p,\ e_{1}\ge 2$. If $i=F_{F_{u_{p^1}}}=(F_{p_{1}^2}\ \cdot\ F_{p_{2}^{e_{2}}}\ \cdot\ ...\ F_{p_{n}^{e_{n}}}\ \cdot\ \prod{})$ then, can the entry point of $i$ still equal the same index, ie $u_{(F_{F_{u_{p^1}}})}=F_{u_{p^1}}$? Answer No. Proof $u_i=\operatorname{lcm}[p_{1}^{2},\ p_{2}^{e_{2}},\ ...\ p_{n}^{e_{n}},\ F_{u_{p^1}}]=\operatorname{lcm}[p_{1}^{2},\ p_{2}^{e_{2}},\ ...\ p_{n}^{e_{n}}]\neq F_{u_{p^1}}=F_{p\cdot u_{p^1}}$ Since any extra powers of $p_{1}$, produce a later entry point, thus $F_{p^2}$ does not appear as a factor, in this configuration, until a later Fibonacci number, ie $F_{F_{p\cdot u_{p^1}}}=F_{F_{u_{p^2}}}$. While the factor, $j=(F_{p_{1}^1}\ \cdot\ F_{p_{2}^{e_{2}}}\ \cdot\ ...\ F_{p_{n}^{e_{n}}}\ \cdot\ \prod{})$ always has an entry point of, $u_j=\operatorname{lcm}[p_{1}^1,\ p_{2}^{e_{2}},\ ...\ p_{n}^{e_{n}},\ F_{u_{p^1}}]=\operatorname{lcm}[p_{1}^1,\ p_{2}^{e_{2}},\ ...\ p_{n}^{e_{n}}]=F_{u_{p^1}}$.

• Are you sure that this incoherent avalanche of formulae answers the question? The edit history of this post is terrifying, too. Why don't you just delete this? – Alex M. Nov 28 '16 at 18:28
• Yes, well actually this does shed light on the fundamental issue, and it would be premature to judge it on its edit history. Saying it is incoherent is just a blatant personal attack(one that you would not say to someone's face), and shows that you don't know much about the subject in particular. Don't feel bad though, since you are not alone. – primedivine Nov 28 '16 at 18:55