Check if the number is a result of multiplying two fibonacci numbers

Question

Is there a way to check if a given number is a result of multiplication of two fibonacci numbers? Any theory/characteristics allowing to quickly decline some of these given numbers?

Answer 1

Let's assume that your $n$ is the product of two large Fibonacci numbers, $f_1$ and $f_2$, hence $ n = f_1 \cdot f_2$ (you can use trial division for the first small numbers). Then we know that $$ f_1 \approx \frac{1}{\sqrt 5} \phi^{p_1} \quad \text{and} \quad f_2 \approx \frac{1}{\sqrt 5} \phi^{p_2} $$ where $\phi $ is the golden ratio.
So we know that $\log_{\phi} 5n$ must be very close to an integer.
Note that this is only a necessary condition: Eg. if one of the numbers is very close to a Fibonacci number, then $\log_{\phi} 5n $ will still be very close to an integer. But you will know a lot about the possible form of the Fibonacci-factorization: Namely $p_1 + p_2 \approx \log_{\phi} 5n$. From there you can easily brute-force your search.

Answer 2

Fibonacci numbers can be written as $F_n=\frac1{\sqrt 5}(\phi^n+\psi^n)$ with $\phi=\frac{1+\sqrt 5}{2}$, $\psi=\frac{1-\sqrt 5}{2}$. Thus $$5F_nF_m=\phi^{n+m}+\phi^n\psi^m+\psi^n\phi^m+\psi^{m+n}$$ If $n>m$, this becomes (using $\phi\psi=-1$) $$5F_nF_m=\phi^{n+m}+\phi^{n-m}(-1)^m+\psi^{n-m}(-1)^m+\psi^{m+n}$$ So the idea is:

• Compute $k=\left\lfloor\frac12+\frac{\ln 5x}{\ln\phi}\right\rfloor $. This should be $n+m$.
• With $y=5x-\phi^k$ compute $d=\left\lfloor\frac12+\frac{\ln |y|}{\ln\phi}\right\rfloor $. If at all, we should have $n=\frac{k+d}{2}$, $m=\frac{k-d}2$ (especially, if $k+d$ is odd$, there is no solution)

Since this approach relies on smallness of both $\psi^{n-m}$ and $\psi^{m+n}$, one should check specifically if $x=F_k =F_kF_1$ or $x=F_{k/2}^2=F_k\pm1$ (may happen if $y$ is small).