# Fibonacci divisibilty properties $F_n\mid F_{kn},\,$ $\, \gcd(F_n,F_m) = F_{\gcd(n,m)}$

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.
• For a start, see the Wikipedia page, Primes and Divisibility section. – Bill Dubuque Aug 28 '11 at 15:41
• I have seen and I don't think it will good help in writing a single proof for all the cited results. – Gandhi Aug 29 '11 at 6:14
• You can read more about Pisano period at wikipedia and in this MO answer. – Martin Sleziak Aug 29 '11 at 9:44
• @Gandhi The first sentence at Bill's link, "...Every $k$th number of the sequence is a multiple of $F(k)$" gives you an immediate proof of all your results. – user940 Aug 29 '11 at 12:30
• Byron schmuland! Still I couldn't get the Bill's link. could you explain, how the link supports to write a proof for all my result. – Gandhi Aug 29 '11 at 13:51

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, 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\,F_n = F_{n-m+1}\,F_m + F_{n-m}\,F_{m-1}\!\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.\,$ Thus $\rm\ (\color{#c00}{f_n},\,f_m)\, =\, (\color{#c00}{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}$$

• I know this. But, I am looking a single proof, which will generalize the whole part of my post. – Gandhi Aug 29 '11 at 6:08
• @Gandhi But it does yield all your statements - see my edit above. – Bill Dubuque Aug 29 '11 at 15:42
• Thank you for this divisibility property and better explanation. – Gandhi Aug 29 '11 at 17:06
• Yes! I understand that. Thank you... – Gandhi Aug 29 '11 at 18:05
• Maybe @Gandhi is looking for the en.wikipedia.org/wiki/Theory_of_everything – The Chaz 2.0 Aug 29 '11 at 22:54

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.

• good and I am looking for a better way if possible. Anyhow, thank you so much for reply – Gandhi Aug 29 '11 at 6:08
• Related : Pisano Period – Yashbhatt Mar 20 '16 at 17:20

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)=LCM(D(a), D(b))$ (thanks to hardmath for the correction). In other words, $D$ 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.

• +1 Moving my comment here, because it is closely related to David's answer. In the case $p>5, p\equiv\pm2\pmod{5}$ an observation we can make immediately is that the "numbers" $\tau$ and $-\tau^{-1}$ are then conjugate under the Frobenius automorphism of the finite field $GF(p^2)$. So $$\tau^p=-\frac{1}{\tau}\in GF(p^2).$$ This implies that both the conjugates are roots of unity of order that is a factor of $2(p+1)$ in $GF(p^2)$. Therefore also the shortest period of the Fibonacci sequence modulo $p$ is a factor of $2(p+1)$. This is much better than the $(p^2-1)$ I promised earlier. – Jyrki Lahtonen Jun 14 '12 at 13:37

The general proof of this is that the fibonacci numbers arise from the expression $$F_n \sqrt{-5} = (\frac 12\sqrt{-5}+\frac 12\sqrt{-1})^n - (\frac 12\sqrt{-5}-\frac 12\sqrt{-1})^n$$

Since this is an example of the general $a^n-b^n$, which $a^m-b^m$ divides, if $m \mid n$, it follows that there is a unique number, generally coprime with the rest, for each number. Some of the smaller ones will be $1$.

The exception is that if $f_n$ is this unique factor, such that $F_n = \prod_{m \mid n} f_n$, then $f_n$ and $f_{np^x}$ share a common divisor $p$, if $p$ divides either. So for example, $f_8=7$, and $f_{56}=7*14503$, share a common divisor of $7$. This means that modulo over $49$ must evidently work too. So $f_{12} = 6$, shares a common divisor with both $f_4=3$ and $f_3 = 4$, is unique in connecting to two different primes.

Gauss's law of quadratic recriprocality applies to the fibonacci numbers, but it's a little more complex than for regular bases. Relative to the fibonacci series, reduce modulo 20, to 'upper' vs 'lower' and 'long' vs 'short'. For this section, 2 is as 7, and 5 as 1, modulo 20.

Primes that reduce to 3, 7, 13 and 17 are 'upper' primes, which means that their period divides $p+1$. Primes ending in 1, 9, 11, 19 are lower primes, meaning that their periods divide $p-1$.

The primes in 1, 9, 13, 17 are 'short', which means that the period divides the maximum allowed, an even number of times. For 3, 7, 11, 19, it divides the period an odd number of times. This means that all odd fibonacci numbers can be expressed as the sum of two squares, such as $233 = 8^2 + 13^2$, or generally $F_{2n+1} = F^2_n + F^2_{n+1}$

So a prime like $107$, which reduces to $7$, would have an indicated period dividing $108$ an odd number of times. Its actual period is $36$. A prime like $109$ divides $108$ an even number of times, so its period is a divisor of $54$. Its actual period is $27$.

A prime like $113$ is indicated to be upper and short, which means that it divides $114$ an even number of times. It actually has a period of $19$.

Artin's constant applies here as well. This means that these rules correctly find some 3/4 of all of the periods exactly. The next prime in this progression, $127$, actually has the indicated period for an upper long: 128. So does $131$ (lower long), $137$ (upper short, at 69). Likewise $101$ (lower short) and $103$ (upper long) show the maximum periods indicated.

No prime under $20*120^4$ exists, where if $p$ divides some $F_n$, so does $p^2$. This does not preclude the existance of such a number.

• I upvoted your Answer because it broaches some interesting points, but Binet's formula where you begin doesn't require square roots of negative numbers. Also I like the connection you start to make at the end with Wall-Sun-Sun primes, whose existence as you suggest is still open, but consider a little more precision in statement, such as "whenever $p$ divides $F_n$, $p^2$ also divides $F_n$". – hardmath Mar 22 '14 at 17:51
• The fibonacci numbers are the rep-units of the smallest of a class of bases which are similar to regular ones. Since heron's triangles are an exmaple of this the last para would indicate that where 103 divides a heron number, so does its square. The term i use for this is sevenite. @hardmath – wendy.krieger Mar 22 '14 at 22:07
• The reason that we use square-root of negative numbers, is that the general base formula $a^n-b^n$ works when negative numbers are used here. – wendy.krieger Nov 20 '19 at 8:43

I found that @David's answer here is very clear to understand, but he omitted some minor details. I reproduce @David's answer with full details. All credits are given to @David.

Lemmas:

$f_{s+t}=f_{s-1}f_t+f_sf_{t+1}$ (I presented a proof for this lemma here)

$s\mid t\implies f_s\mid f_t$ (One user presented a proof here)

Let $g=\gcd(m,n)$ and $d$ be any common divisor of $f_m,f_n$. From the definition of Greatest Common Divisor, it's clear that $$\gcd(f_m, f_n) = f_{\gcd(n, m)}=f_g\iff\begin{cases} f_g\mid f_m\text{ and } f_g\mid f_n\\d\space\space\mid f_g\end{cases}$$

1. $f_g\mid f_m\text{ and } f_g\mid f_n$

From the second lemma and the fact that $g=\gcd(m,n)$, we have $$g\mid m\Rightarrow f_g\mid f_m\quad\hbox{and}\quad g\mid n\Rightarrow f_g\mid f_n$$.

1. $d\mid f_g$

From Bézout's identity, there exists $x,y\in\mathbb Z$ such that $g=mx+ny$.

$f_m\mid f_{mx}$ and $d\mid f_m\implies d\mid f_{mx}$. Similarly, $d\mid f_{ny}$. Thus $d\mid f_{mx-1}f_{ny}+f_{mx}f_{ny+1}$, and from the second lemma $d\mid f_{mx+ny}$, or equivalently $d\mid f_g$.

• This argument is not correct without any mention of how to deal with negative coef's $\,x,y\,$ in the Bezout identity $\,g = mx+ny,\,$ hence negative indexed $f_j$ in the fib's from the addition law for $\,f_g.\,$ Indeed, you mention this problem in comments on David's answer that you repost above. It is puzzling why you would repost an incorrect or incomplete answer with no mention of that problem. – Bill Dubuque Nov 19 '19 at 15:35