Are there infinite Fibonacci primes if and only if there are infinite Fibonacci numbers that are Fibonacci pseudoprimes?

392 Views Asked by At

One of the open questions about the Fibonacci numbers is if there are infinite prime numbers inside the Fibonacci sequence. I wonder if a good approach would be trying to know first if there are infinite odd Fibonacci numbers that are Fibonacci pseudoprimes (the condition is not so strict).

There is a very well known Fibonacci (Lucas) primality test, to verify if a number $n$ is a prime number (but there is also a infinite set of Fibonacci pseudoprimes) that can be applied over the Fibonacci numbers as well: the nth Fibonacci number $F(n)$ is at least a Fibonacci pseudoprime if and only if its associated Fibonacci number, which is the $F(n)^{th}$ Fibonacci number, $F(F(n))$ verifies the Fibonacci primality test condition.

Does somebody knows if that approach has been studied?

I am currently reading "Fibonacci Numbers" of Nikolai Nikolaevich Vorob'ev (recommended!) and this topic is explained briefly as an open issue but no clues about the current status. I have reviewed other questions in the forum and I did not find any reference to the Fibonacci pseudoprimes idea I am writing here. Thanks in advance for any comments, references or help.

UPDATE 2015/04/07

So far I have tried to advance and learn more as follows:

(a) It is already proved that $F(p)$ could be (pseudo)prime if and only if $p$ is prime.

(b) The Fibonacci (pseudo)primality rules for $p$, $F(p)$ are:

  1. If $p \equiv 1,4\ mod\ 5$, then $F(p) \equiv 1\ mod\ p$, and $p$ is at least Fibonacci pseudoprime.
  2. If $p \equiv 2,3\ mod\ 5$, then $F(p) \equiv p-1\ mod\ p$, and $p$ is at least Fibonacci pseudoprime.

(c) This same rule applied to F(F(p)) looks like this:

  1. If $F(p) \equiv 1,4\ mod\ 5$, then $F(F(p)) \equiv 1\ mod\ F(p)$, and $F(p)$ is at least Fibonacci pseudoprime.
  2. If $F(p) \equiv 2,3\ mod\ 5$, then $F(F(p)) \equiv F(p)-1\ mod\ F(p)$, and $F(p)$ is at least Fibonacci pseudoprime.

(d) By reviewing directly the definitions of modularity, it is possible to verify the primality of $F(F(p))$ directly in terms of $p$ as follows:

$F(p) = p*k_1+n,\ k_1 \in \Bbb N, k_1 \gt 0$

$F(F(p)) = F(p)*k_2+n,\ k_2 \in \Bbb N, k_2 \gt 0$

where $n$ can be only $1$ or $p-1$ if the (pseudo)primality is true.

thus,

$F(F(p)) = (p*k_1+n)*k_2+n = p*k_1*k_2+n*k_2+n = p*k_3+n*(k_2+1)$

$k_1*k_2=k_3 \in \Bbb N, k_3 \gt 0$

finally $F(F(p))$ would be at least a Fibonacci pseudoprime if and only if:

$F(F(p)) \equiv n*(k_2+1) \mod p$, for $n=1$ or $n=p-1$.

where $k_2 = \lfloor\frac{F(F(p))}{F(p)}\rfloor$

E.g:

$p=11$ and $F(p)=89$. Both are $\equiv 1,4\ mod\ 5$.

$F(p)=89 \equiv 1\ mod\ 11$, so $p=11$ is at least a Fibonacci pseudoprime.

If $p=11$ is at least a Fibonacci pseudoprime then $F(11) = 89$ could also be a Fibonacci pseudoprime.

By direct primality test $F(89)=1779979416004714189 \equiv 1\ mod\ 89$, so $F(p)=89$ is at least a Fibonacci pseudoprime.

So applying (d): $F(11) = 89$ is at least a Fibonacci pseudoprime if and only if:

$\ \ \ $a. $F(F(11)) \equiv n*(k_2+1) \mod 11$, and

$\ \ \ $b. $ n*(k_2+1) \mod 11 = (F(F(p))\ mod\ p)$

In this case $n=1$, so if the following $(a)=(b)$ is true, the pseudoprimality is true:

$(k_2+1)\equiv 1(a)\ mod\ 11$

$F(F(11))\equiv 1(b) \ mod\ 11$

where $k_2 = \lfloor\frac{1779979416004714189}{89}\rfloor=1999768719154092$

Both congruences are the same one, $1$, so in this case $89$ is also at least a pseudoprime.

Next steps: trying to understand the properties (d) of the direct relationship between $p$ and $F(F(p))$.