Cómo mostrar que cuando se $F_n$ se divide por $F_m$($n>m$),a continuación, el resto r es el número de Fibonacci o $F_m -r$ es un número de Fibonacci?

Question

Cómo mostrar que cuando se $F_n$ se divide por $F_m$($n>m$),a continuación, el resto r es el número de Fibonacci o $F_m -r$ es un número de Fibonacci?

En aplicar el algoritmo de la División,obtenemos

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

Cómo proceder en el futuro?

EDITAR

Si podemos demostrar que tanto $F_m-r$ $r$ ambos no son de Fibonacci número, a continuación, $F_m $ no está de Fibonacci número, a continuación, se realiza?

Answer 1

Extendamos la definición de los números de Fibonacci a índices negativos, tales que $$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$.

Introducir los números de Lucas $L_n$, de tal manera que $$L_n=L_{n-1}+L_{n-2}$$ with $L_0 =2$ and $L_1=1$.

Tenemos : \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*}

Prueba: desde ambos lados de estas dos identidades satisfacer el mismo segundo orden lineal de las recurrencias en el índice de $m$, con el fin de demostrarlo, basta para comprobar que se mantenga en$m=0$$m=1$. Para $m=0$ es claro que \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*} Para $m=1$ tenemos que demostrar que \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*} Pero estos son fácilmente verificada en $j=1$ $j=2$ y, a continuación, se mantenga para todas las $j$, ya que ambas cumplen la misma de segundo orden lineal de recurrencia en $j$.

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

Deje $n= j+m >m$

A continuación, $$\tag{1}\label{1} F_{n} \equiv (-1)^mF_{n-2m} \pmod {F_m} $ $ -1 - Si $m<n<2m$, ya que el $ F_{n-2m}=(-1)^{2m+1-n}F_{2m-n} $, tenemos

$$\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 - Si $n\ge 2m$, vamos a $n=k(2m)+s$$0\le s<2m$$k\ge 1$. A continuación, se sigue de $\eqref{1}$, que $$ F_{n} \equiv (-1)^{km}F_{s} \pmod {F_m}$$ Si $2m>s>m$, se desprende $\eqref{2}$ que $ F_s\equiv (-1)^{m+1-s}F_{2m-s} \bmod {F_m} $

entonces

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

De lo contrario, $$ F_{n} \equiv (-1)^{km}F_{s} \pmod {F_m}$$ con $0\le F_{s}<F_m$

En cualquier caso, no existe $h,\epsilon $ $0\le h<m$ $\epsilon= \pm 1$ tal que $F_n \equiv \epsilon F_h \bmod F_m$.

Si $\epsilon=1$, $r= F_h$, y si $\epsilon=-1$, $F_m-r= F_h$.