Prove that $9\vert F_{n+24}$ iff $9\vert F_n$.

Question

Prove that $9\vert F_{n+24}$ iff $9\vert F_n$.

This can be proved if in some way we can establish $F_{n+24}\equiv F_{n}(mod 9)$.

It is given in hint to use identity $F_{m+n}=F_{m-1}F_{n}+F_{m}F_{n+1}$.

Using the above identity for $F_{n+24}$,we get $F_{n+24}=F_{n-1}F_{24}+F_{n}F_{25}$,from here how to find the direction leading to $F_{n+24}\equiv F_{24}(mod 9)$?

Answer 1

Just note that $F_{24} \equiv 0 \bmod 9$ and $F_{25} \equiv 1 \bmod 9$, and so $F_{n+24} = F_{n-1}F_{24}+F_{n}F_{25} \equiv F_{n} \bmod 9$. In particular, $9 \mid F_{n+24}$ iff $9 \mid F_n$.

Actually, we have $9 \mid F_{n+12}$ iff $9 \mid F_n$ because $F_{12} \equiv 0 \bmod 9$ and $F_{13} \equiv -1 \bmod 9$ gives $F_{n+12} = F_{n-1}F_{12}+F_{n}F_{13} \equiv -F_{n} \bmod 9$.

More generally, take a divisor $d$ of $F_m$. Then, $d \mid F_{n+m}$ iff $d \mid F_n$.

Indeed, $F_{n+m}=F_{m+n}=F_{m-1}F_{n}+F_{m}F_{n+1} \equiv F_{m-1}F_{n}\bmod d$. But $F_{m-1}$ is invertible mod $d$ because $\gcd(F_{m-1},F_m)=1$.

Answer 2

Use $$F_{n+24}=F_{(n+12)+12}=F_{n+11}F_{12}+F_{n+12}F_{13}$$ and the fact that $9| F_{12}$ but $9$ does not divide $F_{13}$ to show that $9|F_{n+24}$ iff $9|F_{n+12}$. Then use similar identity to prove that $9|F_{n+12}$ iff $9|F_n$.