5
$\begingroup$

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?

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.