# 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?

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?

• someone please try using its contrapositive? – Styles May 10 '18 at 18:45
• Where does this problem come from? – lhf May 10 '18 at 23:34
• @lhf:Burton's elementary number theory – Styles May 11 '18 at 2:22
• What is the contrapositive of the above statement? – Styles May 11 '18 at 12:43

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