Can any one give a generalization of the following properties in a single proof? I have checked the results, which I have given below by trial and error method. I am looking for a general proof, which will cover the all my results below:
- Every third Fibonacci number is even.
- 3 divides every 4th Fibonacci number.
- 5 divides every 5th Fibonacci number.
- 4 divides every 6th Fibonacci number.
- 13 divides every 7th Fibonacci number.
- 7 divides every 8th Fibonacci number.
- 17 divides every 9th Fibonacci number.
- 11 divides every 10th Fibonacci number.
- 6, 9, 12 and 16 divides every 12th Fibonacci number.
- 29 divides every 14th Fibonacci number.
- 10 and 61 divides every 15th Fibonacci number.
- 15 divides every 20th Fibonacci number.
Best Answer
Many of the divisibility properties of Fibonacci numbers follow from the fact that they comprise a divisibility sequence, i.e. $\rm\,m\,|\,n\ \Rightarrow\ F_m\,|\,F_n.\,$ All of your statements above are special cases of this, e.g. $\rm\,F_{15} = 610,\,$ so $\rm\,15\,|\,n\ \Rightarrow\ F_{15}\,|\,F_n\,\Rightarrow\,610\,|\,F_n,\,$ which is precisely your statement $11,\,$ that $10$ and $61$ divide every $15\,$'th Fibonacci number.
In fact $\rm\,F_n\,$ is strong divisibility sequence, i.e. $\rm\,(F_m,F_n) = F_{(m,n)},\,$ i.e. $\rm\,gcd(F_m,F_n) = F_{\gcd(m,n)}.\,$ This stronger property specializes to the above property if $\rm\,m\mid n\,\ (\!\!\iff \gcd(m,n) = m\,\!).\,$ The proof is not difficult. Here is a straightforward way to proceed. Recall the Fibonacci addition law $\rm\,F_{n+m} =F_{n+1}\,F_m + F_n\,F_{m-1}.\,$ Applying the shift $\rm\,n\to n-m\ $ this addition law becomes $\rm\,\color{#c00}{F_n} = F_{n-m+1}\,F_m + F_{n-m}\,F_{m-1}\!\color{#c00}{\equiv F_{n-m}\,F_{m-1}}\pmod{\!F_m}.\,$ So for $\rm\,k=m-1\,$ we may invoke the Theorem below to conclude that $\rm\,f_n = F_n\,$ is a strong divisibility sequence.
Theorem $ $ Let $\rm\ f_n\, $ be an integer sequence such that $\rm\ f_{\:\!0} =\, 0,\ f_1 = 1\ $ and such that for all $\rm\,n > m\,$ holds $\rm\ \, \color{#c00}{f_n\equiv\, f_{\,k}\ f_{n-m}}\,\ (mod\ f_m)\ $ for some $\rm\,k < n,\ (k,m)\, =\, 1.\, $ Then $\rm\ (f_n,f_m) = f_{\,(n,\,m)} $
Proof $\ $ By induction on $\rm\,n + m.\,$ The theorem is trivially true if $\rm\ n = m\ $ or $\rm\ n = 0\ $ or $\rm\, m = 0.\,$ Assume wlog $\rm\,n > m > 0.\,$ Since $\rm\,k\!+\!m < n\!+\!m,\,$ by induction $\rm\,(f_{\,k},f_m)=f_{\,(k,\,m)}\!=\,f_1 = 1.\,$ So $\rm\ (\color{#c00}{f_n},\,f_m)\overset{\color{#90f}R}=\ (\color{#c00}{f_{\,k}\,f_{n-m}},\,f_m)\, \!\overset{\color{#0a0}E}= (f_{n-m},\,f_m)\, =\, f_{\,(n-m,\,m)} =\, f_{\,(n,\,m)} $ follows by induction (which applies here since $\rm\,(n-m)+m\, <\, n+m\,\!),\,$ and by employing well-known gcd laws, namely $\rm\,\color{#90f}R\!:\ (\color{#c00}a,b) = (\color{#c00}a',\,b)\ \ if\ \ \color{#c00}{a\equiv a'}\pmod{b}\ $ and $\rm\,\color{#0a0}E\!:\ (\color{c00}c\:\!a,b) = (a,b)\,$ if $\rm\,(c,b) = 1.\ \ $ QED
You may find it insightful to simultaneously examine other strong divisibility sequences, e.g. see my this post on $\rm\,f_n = (x^n-1)/(x-1).\,$ In this case $\rm\, \gcd(f_m,f_n) = f_{\,\gcd(m,n)}\,$ may be interpreted as a $\rm\,q$-analog of the integer Bezout identity, for example
$$\begin{align} \rm\displaystyle\ \color{#c00}3 = (\color{#0a0}{15},\color{#90f}{21})\,\ \leadsto\,\ f_{\:\!\large\color{#c00}3\,} &\rm =\, a\, f_{\:\!\large\color{#0a0}{15}}+b\, f_{\:\!\large\color{#90f}{21}},\,\ \text{explicitly:}\\[.3em] \rm \frac{x^{\large \color{#c00}3}-1}{x-1} \,&\rm =\, (x^{{15}} + x^9 + 1)\, \frac{x^{\large\color{#0a0}{15}}-1}{x-1} - (x^9+x^3)\, \frac{x^{\large\color{#90f}{21}}-1}{x-1} \end{align}\qquad$$
Generally see this answer for $\rm\, f_n = (x^n-y^n)/(x-y)$.