[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 such that

First few terms of Fibonacci sequence are

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 -th month (denoted by ) is sum of pairs alive in the previous -th month and number of newly born offspring. By assumption, any pair produces offspring after 2 month, thus recurrence relation is

given that , which is nothing but relation of Fibonacci sequence we defined earlier. So in one year, there will be total 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; .

---

2. Greatest Common Divisor of Fibonacci numbers

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

First let's look at some examples.

1. If we take , then . Woops! the greatest common divisor is nothing but .

2. If we take , then , so that

3. If we take , then so that (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

for . For convenience, put . Then the recurrence relation for Fibonacci sequence gives

so that

Since , luckily enough, our closed form expression for is

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

The matrix multiplication is associative, so that

Using closed form expression for , we obtain a striking fact,

or equivalently,

Comparing entries,

---

---

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 where are positive integers. First, fix .

• If , . So trivially, divides . Does divide for all values of ?

• Suppose this holds for some . Now using the clever identity,

Since we assumed , the righthand side should be divisible by and so does by induction. In conlcusion

---

---

Remember the first example ? Since , we obtain without direct calculation of !

5. General Case?

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

Again using our clever identity,

. Here we must observe two things.

1. is divisible by (by result of previous section), so we can cancel out the term when considering greatest common divisor .

2. Next we should examine . Denote this value as . Since , we have , so that

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

---

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

where each denote the remainders. Therefore,

The last equation, tells us that is divisible by ; thus using result from Section 4, we get

where . Therefore, the ultimate relationship between two Fibonacci numbers, can be summarized as

---

---

Let's verify this final result using examples above.

• 

• 

Good!

6. Fibonacci Primes

Interestingly, the converse of results obtained from Section 4 can be derived using our ultimate relationship, .

If , then which is equivalent to saying

So in the Fibonacci sequence, the following is true.

---

---

This brings up the question,

Are there any fibonacci numbers that are also prime numbers?

Above fact indicates that only possibilities are where is a prime (except ) . 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. is prime for 8 of the first 10 primes ; the exceptions are . However, Fibonacci primes become rarer as the index increases. is prime for only 26 of the 1,229 primes 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

• Greatest common divisor of two fibonacci numbers is equal to fibonacci number indexed by the greatest common divisor of two indices .

• 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.