[1]

Relationship between Fibonacci numbers

1. The History

We all know what Fibonacci sequence is, but to be sure, let's just state the full recurrence relation here. A Fibonacci sequence is collection of integers $\left\{ F_n \right\}$ such that

$F_1 = F_2 = 1,\ F_n = F_{n-1} + F_{n-2}\ (n \geq 3)$

First few terms of Fibonacci sequence are

$1,1,2,3,5,8,13,21,34,55,89,144,...$

The sequence first appeared on the book Liber Abaci by Leonardo of Pisa (known as Fibonacci). Fibonacci posed an idealized growth of rabbit population as follows.

A single pair of rabbits (one male, and other one female) born.
Rabbits are able to mate at age of 1 month, and 1 month after the mating, female produce another pair (also one male and other one female) of rabbits.
Rabbits never die nor stop mating so that every pair of rabbits produce their offspring indefinitely.

Then the question Fibonacci proposed was

How many pairs will there be in one year?

Clearly, the total number of rabbit pairs in $n$ -th month (denoted by $F_n$ ) is sum of pairs alive in the previous $(n-1)$ -th month and number of newly born offspring. By assumption, any pair produces offspring after 2 month, thus recurrence relation is

$F_n = F_{n-1} + F_{n-2}$

given that $F_1 = F_2 = 1$ , which is nothing but relation of Fibonacci sequence we defined earlier. So in one year, there will be total $F_{12} = 144$ pairs of rabbits.

What I like to talk about in this post is not the implementation of Fibonacci sequence in real world, but the relationship between the terms in Fibonacci sequence; $\left\{ F_n \right\}$ .

2. Greatest Common Divisor of Fibonacci numbers

The goal of this post is to find the greatest common divisor of two fibonacci numbers, $F_n, F_m$

$\gcd(F_n, F_m)$

First let's look at some examples.

If we take $n = 5, m = 10$ , then $F_5 = 5, F_{10} = 55$ . Woops! the greatest common divisor is nothing but $F_5 = 5$ .
If we take $n = 8, m = 20$ , then $F_8 = 21,\ F_{20} = 6765$ , so that $\gcd(F_8, F_{20}) = 3 = F_4$
If we take $n = 11,\ m = 21$ , then $F_{11} = 89,\ F_{21} = 10946$ so that $\gcd(F_{11}, F_{21}) = 1= F_1$ (relatively prime).

As you can see, the greatest common divisor of two fibonacci numbers is also another fibonacci number. Is this mere coincidence? Well let's find out.

3. Clever Identity

First, let's use matrix to represent the recurrence relation. Define a 2 by 2 matrix

$\mathbf{F}_n = \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1} \end{pmatrix}$

for $n \geq 1$ . For convenience, put $F_0 = 0$ . Then the recurrence relation for Fibonacci sequence gives

$\begin{pmatrix} F_{n+2} & F_{n+1}\\ F_{n+1} & F_n \end{pmatrix} = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}\begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1} \end{pmatrix}$

so that

$\mathbf{F}_{n+1} = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}\mathbf{F}_n$

Since $\mathbf{F}_1 = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}$ , luckily enough, our closed form expression for $\mathbf{F}_n$ is

$\mathbf{F}_n = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^n$

using iterated multiplication of square matrix. Now, here comes the clever trick. Put $n +m$ instead of $n$ . Then our formula becomes

$\mathbf{F}_{n+m} = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^{n+m}$

The matrix multiplication is associative, so that

$\begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^{n+m} = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^{n} \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^{m}$

Using closed form expression for $\mathbf{F}_n,\ \mathbf{F}_m$ , we obtain a striking fact,

$\mathbf{F}_{n+m} = \mathbf{F}_n \mathbf{F}_m$

or equivalently,

$\begin{pmatrix} F_{n+m+1} & F_{n+m}\\ F_{n+m} & F_{n+m-1} \end{pmatrix} = \begin{pmatrix} F_{n+1} & F_n\\ F_n & F_{n-1} \end{pmatrix} \begin{pmatrix} F_{m+1} & F_m\\ F_m & F_{m-1} \end{pmatrix}$

Comparing $(2,1)$ entries,

$F_{n+m} = F_n F_{m+1} + F_{n-1}F_m$

This simple looking relationship is indeed very useful, as we will use in further sections.

4. Divisibility?

Let's think about Fibonacci numbers of the form $F_{mn}$ where $m,n$ are positive integers. First, fix $n$ .

If $m=1$ , $F_{mn} = F_n$ . So trivially, $F_n$ divides $F_{mn}$ . Does $F_n$ divide $F_{mn}$ for all values of $m$ ?
Suppose this holds for some $m$ . Now using the clever identity,

$F_{(m+1)n} = F_{mn}F_{n+1} + F_{mn-1}F_n$

Since we assumed $F_n | F_{mn}$ , the righthand side should be divisible by $F_n$ and so does $F_{(m+1)n}$ by induction. In conlcusion

$\gcd(F_n, F_{mn}) = F_n$

Remember the first example $F_5, F_{10}$ ? Since $10 = 2 \times 5$ , we obtain $\gcd(F_5, F_{10}) = F_5 = 5$ without direct calculation of $F_{10}$ !

5. General Case?

Now let's think about more general case when $n > m$ but $n$ is NOT divisible by $m$ . Then using division alogrithm for integers, there exist unique quotient and remainder $q$ and $r$ such that

$n = mq +r\ (0 < r < m)$

Again using our clever identity,

$F_n = F_{mq + r} = F_{mq}F_{r+1} + F_{mq-1}F_{r}$

. Here we must observe two things.

$F_{mq}$ is divisible by $F_m$ (by result of previous section), so we can cancel out the term $F_{mq}F_{r+1}$ when considering greatest common divisor $\gcd(F_n, F_m)$ .
Next we should examine $\gcd(F_{mq-1}, F_m)$ . Denote this value as $d$ . Since $F_m | F_{mq}$ , we have $d | F_{mq}$ , so that

$d | \gcd(F_{mq}, F_{mq-1})$

But a common divisor of the successive Fibonacci numbers is 1 (since two are relatively prime), so that $d = 1$ . Thus

$\gcd(F_n, F_m) = \gcd(F_r, F_m)$

We can reduce the index by repeated application of divisor algorithm between integers!

The Euclidean Algorithm ensures this repeated application of divisor algorithm ends in finite step, so that we can write a sequence of equations of the form

$\begin{align*} n = mq + r \\ m = rq_1 + r_1 \\ r = r_1q_2 + r_2\\ ...\\ r_k = r_{k+1} q_{k+1} + 0 \end{align*}$

where each $r_1,r_2,...$ denote the remainders. Therefore,

$\begin{align*} \gcd(F_n, F_m) &= \gcd(F_r, F_m) \\ &= \gcd(F_r, F_{r_1}) \\ &= \gcd(F_{r_1}, F_{r_2}) \\ &= ... \\ &= \gcd(F_{r_k}, F_{r_{k+1}}) \end{align*}$

The last equation, $r_k = r_{k+1}q_{k+1}$ tells us that $F_{r_k}$ is divisible by $F_{r_{k+1}}$ ; thus using result from Section 4, we get

$\gcd(F_{r_k}, F_{r_{k+1}})= F_{r_{k+1}}$

where $r_{k+1} = \gcd(n, m)$ . Therefore, the ultimate relationship between two Fibonacci numbers, can be summarized as

$\gcd(F_n, F_m) = F_{\gcd(n,m)}$

Let's verify this final result using examples above.

$\gcd(F_8, F_{20}) = F_{\gcd(8, 20)} = F_4$
$\gcd(F_{11}, F_{21}) = F_{\gcd(11, 21)} = F_1$

Good!

6. Fibonacci Primes

Interestingly, the converse of results obtained from Section 4 can be derived using our ultimate relationship, $\gcd(F_n, F_m) = F_{\gcd(n,m)}$ .

If $F_n\ |\ F_m$ , then $\gcd(F_n, F_m) = F_{\gcd(n,m)} = F_n$ which is equivalent to saying

$\gcd(n,m) = n \implies n\ |\ m$

So in the Fibonacci sequence, the following is true.

$F_n\ |\ F_m \iff n\ |\ m\ (\text{for all }m \geq n \geq 3)$

This brings up the question,

Are there any fibonacci numbers that are also prime numbers?

Above fact indicates that only possibilities are $F_p$ where $p$ is a prime (except $F_4 = 3$ ) . The first 15 fibonacci primes are -[2]

p	F_p
3	2
4	3
5	5
7	13
11	89
13	233
17	1,597
23	28,657
29	514,229
43	433,494,437
47	2,971,215,073
83	99,194,853,094,755,497
131	1,066,340,417,491,710,595,814,572,169
137	9,134,702,400,093,278,081,449,423,917

Fibonacci primes become rarer as the index increases. $F_p$ is prime for 8 of the first 10 primes $p$ ; the exceptions are $F_2 = 1, F_{19} = 4181=37 \times 113$ . However, Fibonacci primes become rarer as the index increases. $F_p$ is prime for only 26 of the 1,229 primes $p$ below 10,000. We can view Fibonacci primes as building blocks of Fibonacci sequence, since they are not divisible by any Fibonacci numbers less than themselves.

7. Conclusion

Fibonacci sequence grows rapidly, with recurrence relation

$F_1 = F_2 = 1,\ F_n = F_{n-1} + F_{n-2}\ (n \geq 3)$

Greatest common divisor of two fibonacci numbers $F_n, F_m$ is equal to fibonacci number indexed by the greatest common divisor of two indices $n,m$ .
The building blocks of Fibonacci sequence are Fibonacci primes which become rarer as the index increases.

P.S It is NOT known whether there are infinitely many Fibonacci primes... 😕

8. Citations

[1] By Jahobr [CC0], from Wikimedia Commons, Source Link

[2] List of Fibonacci Primes with factorization

Starting from this post, I promise not to use images in the Web without any proper copyright citations. Instead I will use my own drawings and diagrams for explanations. I apologize for any misuses of images related to my previous posts.

Sort:

Trending

[-]

sildude (46) 6 years ago

Nice post. For anyone curous about the largest fibonacci prime, the largest confirmed prime is F₁₀₄₉₁₁ and is a whopping 21925 digits long. Unconfirmed ones are even larger.

$0.04

1 vote

steemitboard (66) 6 years ago

Congratulations @mathsolver! You have completed the following achievement on Steemit and have been rewarded with new badge(s) :

You published a post every day of the week

_{Click on the badge to view your Board of Honor.}
_{If you no longer want to receive notifications, reply to this comment with the word STOP}

To support your work, I also upvoted your post!

You can upvote this notification to help all Steemit users. Learn why here!

$0.00

amansharma555 (46) 6 years ago

Wow great explanation man,keep it up..

Award for the number of upvotes

[Math Talk #20] Fibonacci numbers and their relationships