How to show that when $F_n$ is divided by $F_m$($n>m$),then the remainder r is Fibonacci number or $F_m -r$ is a Fibonacci number?

Question

How to show that when $F_n$ is divided by $F_m$($n>m$),then the remainder r is Fibonacci number or $F_m -r$ is a Fibonacci number?

On applying Division algorithm,we get

$F_n=kF_m+r;0\le r<F_m$

How to proceed further?

EDIT

If we prove that both $F_m-r$ and $r$ both are not Fibonacci number then $F_m $ is not Fibonacci number then we are done?

Answer 1

Let us extend the definition of the Fibonacci numbers to negative indices, such that $$F_{-n}=(-1)^{n+1}F_n$$ so that the same linear second order recurrence $F_n=F_{n-1}+F_{n-2}$ is verified, with the same values at index $0$ and $1$ : $F_0=0$ and $F_1=1$.

Introduce the Lucas numbers $L_n$, such that $$L_n=L_{n-1}+L_{n-2}$$ with $L_0 =2$ and $L_1=1$.

We have : \begin{align*} F_{j+m}&=\frac{1}{2}(F_mL_j+L_mF_j)\\ F_{j-m}&=(-1)^m\frac{1}{2}(L_mF_j-F_mL_j) \end{align*}

Proof: since both sides of these two identities satisfy the same second order linear recurrences on the index $m$, in order to prove them, it suffices to check that they hold at $m=0$ and $m=1$. For $m=0$ it is clear that \begin{align*} F_{j}&=\frac{1}{2}(F_0L_j+L_0F_j)\\ F_{j}&=(-1)^0\frac{1}{2}(L_0F_j-F_0L_j) \end{align*} For $m=1$ we need to prove that \begin{align*} F_{j+1}&=\frac{1}{2}(F_1L_j+L_1F_j)=\frac{1}{2}(L_j+F_j)\\ F_{j-1}&=(-1)^1\frac{1}{2}(L_1F_j-F_1L_j)=\frac{1}{2}(L_j-F_j) \end{align*} But these are easily verified at $j=1$ and $j=2$ and then they hold for all $j$, since both sides also satisfy the same second order linear recurrence on $j$.

Then $$ F_{j+m} -(-1)^mF_{j-m}=F_mL_j$$ Then $$ F_{j+m} \equiv (-1)^mF_{j-m} \pmod {F_m} $$

Let $n= j+m >m$

Then $$\tag{1}\label{1} F_{n} \equiv (-1)^mF_{n-2m} \pmod {F_m} $$ -1- If $m<n<2m$, since $ F_{n-2m}=(-1)^{2m+1-n}F_{2m-n} $, we have

$$\tag{2}\label{2} F_n\equiv (-1)^{m+1-n}F_{2m-n} \pmod {F_m} $$ with $0<F_{2m-n}<F_m$

-2- If $n\ge 2m$, let $n=k(2m)+s$ with $0\le s<2m$ and $k\ge 1$. Then, it follows from $\eqref{1}$, that $$ F_{n} \equiv (-1)^{km}F_{s} \pmod {F_m}$$ If $2m>s>m$, it follows from $\eqref{2}$ that $ F_s\equiv (-1)^{m+1-s}F_{2m-s} \bmod {F_m} $

then

If $2m>s>m$, $$F_n\equiv (-1)^{(k+1)m-s+1}F_{2m-s} \pmod {F_m} $$ with $0<F_{2m-s}<F_m$

Otherwise $$ F_{n} \equiv (-1)^{km}F_{s} \pmod {F_m}$$ with $0\le F_{s}<F_m$

In any case, there exist $h,\epsilon $ with $0\le h<m$ and $\epsilon= \pm 1$ such that $F_n \equiv \epsilon F_h \bmod F_m$.

If $\epsilon=1$ then, $r= F_h$, and if $\epsilon=-1$ then, $F_m-r= F_h$.