Fibonacci modular results

Question

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:

1. Every third Fibonacci number is even.
2. 3 divides every 4th Fibonacci number.
3. 5 divides every 5th Fibonacci number.
4. 4 divides every 6th Fibonacci number.
5. 13 divides every 7th Fibonacci number.
6. 7 divides every 8th Fibonacci number.
7. 17 divides every 9th Fibonacci number.
8. 11 divides every 10th Fibonacci number.
9. 6, 9, 12 and 16 divides every 12th Fibonacci number.
10. 29 divides every 14th Fibonacci number.
11. 10 and 61 divides every 15th Fibonacci number.
12. 15 divides every 20th Fibonacci number.

Answer 1

Most 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 $\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 when $\rm\:m\:|\:n\:\ (\!\iff \gcd(m,n) = m\:\!).\:$ The proof is not difficult. Here is a way straightforward to proceed. Recall the Fibonacci addition law $\rm\:F_{n+m} =F_{n+1}\:F_m + F_n\:F_{m-1}\:.\:$ After applying the shift $\rm\:n\to n-m\ $ this addition law becomes $\rm\:F_n = F_{n-m+1}\:F_m + F_{n-m}\:F_{m-1}\!\equiv F_{n-m}\:F_{m-1}\pmod{F_m}.\:$ Hence 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\ \: f_n\equiv\: f_{\:k}\ f_{n-m}\:\ (mod\ f_m)\ $ with $\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.\:$ So 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.\:$ Thus $\rm\ (f_n,\:f_m)\: =\: (f_{\:k}\:f_{n-m},\:f_m)\: =\: (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\:(a,b) = (a',\:b)\ \ if\ \ a\equiv a'\pmod{b}\ $ and $\rm\:(c\:a,b) = (a,b)\:$ if $\rm\:(c,b) = 1\:.\quad$ QED

You may find it insightful to simultaneously examine other strong divisibility sequences, e.g. see my post here 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 $$\rm\displaystyle\ 3\ =\ (15,21)\ \ \leadsto\ \ \frac{x^3-1}{x-1}\ =\ (x^{15} + x^9 + 1)\ \frac{x^{15}-1}{x-1}\ -\ (x^9+x^3)\ \frac{x^{21}-1}{x-1}$$

Answer 2

I guess that the standard way to understand all these divisibility results in one single swoop is to observe that the Fibonacci sequence modulo any number N becomes periodic.

For instance, Fibonacci modulo 2 is 0, 1, 1, 0, 1, 1, 0, ...... proving the even-ness of $F_n$ for $n=0,3,6,9,...$.

Fibonacci modulo $3$ is 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, ..... making obvious that $3$ divides $F_n$ for $n=0, 4, 8, 12, ...$ .

Try yourself the next ones!

NOTE: the same technique can be applied to any linear recursive sequence with constant coefficients.

Answer 3

As other posters have already indicated, for every positive integer $N$, there is some $D(N)$ such that every $D$-th Fibonacci is divisible by $N$.

The next logical question to my mind is how to compute $D(N)$. Observe that, if $a$ and $b$ are relatively prime, then $D(ab)=D(a) D(b)$ (exercise!). In other words, $D$ is a multiplicative function and is determined by its values for prime powers. I'll talk just about computing $D(p)$ for $p$ a prime.

Recall the formula $$F_n = \frac{1}{\sqrt{5}} \left( \tau^n - (-\tau^{-1})^n \right)$$ where $\tau = (1+\sqrt{5})/2$.

Suppose that the prime $p$ is $\pm 1 \bmod 5$. Then there is a square root of $5$ in $\mathbb{Z}/p$. The above formula is still valid in terms of that square root. For example, if $p=11$, then the square roots of $5$ modulo $11$ are $4$ and $7$. We have $(1+4)/2 \equiv 8 \mod 11$ and $(1+7)/2 \equiv 4 \mod 11$ and, sure enough, $F_n = (1/4) \left( 8^n - 4^n \right) \mod 11$.

So $p$ divides $F_n$ if and only if $\tau^n = (- \tau^{-1})^n$. In other words, we have to compute the order of $- \tau^2$ in the unit group of $\mathbb{Z}/p$. (In the above example, $- \tau^2 \equiv - 4^2 \equiv -64 \equiv 2 \mod 11$, so the conclusion is that $11$ divides $F_n$ if and only if $2^n \equiv 1 \mod 11$.) By Lagrange's theorem, we see that $D(p)$ will divide $p-1$ for $p$ which is $\pm 1 \bmod 5$.

I can say more, but this is really an excellent project for a beginning number theorist to play with for his or herself. What can you say about primes which are $\pm 2 \bmod 5$? What can you say about prime powers? For $p \equiv \pm 1 \mod 5$, when does $D(p)$ divide $(p-1)/2$? There isn't a complete formula here, but there are lots of great things to observe.