Encontrar el resto de $F_n$ cuando se divide por $5$

Question

Deje $\{ F_n\}$ ser la secuencia de números definidos por $F_1=1=F_2;\, F_{n+1}=F_n+F_{n-1}$$n \geq 2$. Deje $f_n$ del resto de la izquierda cuando la $F_n$ se divide por $5$. A continuación, $f_{2000}$ es igual a

(A) $0$ $~~~~~~~~~~~~~~~~$ (B) $1$ $~~~~~~~~~~~~~~~~$ (C) $2$$~~~~~~~~~~~~~~~~$ (D) $3$

He encontrado que $F(1)=1$, $F(2)=1$, $F(3)=2$, $F(4)=3$, $F(5)=5$, $F(6)=8$, $F(7)=13$, $F(8)=21$, $F(9)=34$, y $F(10)=55$. Pero necesito un patrón sistemático para encontrar $F_n$.

Answer 1

$\rm{\bf Sugerencia}\ \ \ mod\ 5\!:\,\ F_{k}\!\equiv\color{#0A0}0\:\Rightarrow\:F_{k+5}\!\equiv\color{#C00}0\ \ \ por\ \ \ \begin{array}{|c|c|c|c|c|c|} \hline \rm k&\rm k\!+\!1 &\rm k\!+\!2 &\rm k\!+\!3 &\rm k\!+\!4 &\rm k\!+\!5\\ \hline \color{#0A0}0&\rm n &\rm n &\rm 2n &\rm 3n &\rm \color{#C00}0 \\\hline\end{array}$

Answer 2

Ahora el patrón para el resto es, $f_{1}=1$, $f_{2}={1}$, $f_{3}={2}$, $f_{4}={3}$ ahora tenemos $f_{5}=0$. Así que este es nuestro primer cero. Si usted procede de esta manera usted va a ver que $f_{10}=0$ $f_{15}=0$ y así sucesivamente. Por eso, $f_{2000}=0$.

Answer 3

$$F_n=F_{n-1}+F_{n-2}=F_{n-2}+F_{n-3}+F_{n-2}=2F_{n-2}+F_{n-1}$$ $$=2(F_{n-3}+F_{n-4})+F_{n-3}=3F_{n-3}+2F_{n-4}$$

$$=3(F_{n-4}+F_{n-5})+2F_{n-4}=5F_{n-4}+3F_{n-5}$$

$$\text{ So,} F_n\equiv 3F_{n-5}\pmod 5 $$

Como $F_1=F_2=1\implies F_0=F_2-F_1=0\equiv0\pmod 5$

$\implies 5\mid F_n$ si $5\mid n$

---

Como alternativa, desde Lema$5$% de esta , $F_n\mid F_m \iff n\mid m\text{ or } n=2$ $m\ge n\ge 1$

Nos encontramos con $F_2=F_1=1,F_3=2,F_4=3, F_5=5$

Por eso, $F_5\mid F_m \iff 5\mid m$ $m\ge1$

Answer 4

Sugerencia:

Demostrar por inducción que $F_n \equiv 2n3^n\mod 5$.

Answer 5

Ya tenemos todas estas buenas respuestas aquí, yo pensé que iba a proporcionar la solución más obvia: \begin{align}f_{2000}=F_{2000}\bmod 5=&42246963333923048787067256023414827825798528402506\\ &81098010280137314308584370130707224123599639141511\\ &08844608753890960360764019471164359602927198331259\\ &87373262535558026069915859152294924539049987222567\\ &95316982874482472992263901833716778060607011615497\\ &88671987985831146887087626459736908672288402365442\\ &22952433479644801395153495629720876526560695298064\\ &99841977448720155612802665404554171717881930324025\\ &204312082516817125\bmod 5=0\end{align}

(Es mucho más fácil de usar$5\mid F_5\mid F_{5\cdot200}$).