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; .
The goal of this post is to find the greatest common divisor of two fibonacci numbers,
First let's look at some examples.
If we take , then
. Woops! the greatest common divisor is nothing but
.
If we take , then
, so that
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.
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.
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
!
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.
is divisible by
(by result of previous section), so we can cancel out the term
when considering greatest common divisor
.
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!
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.
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... 😕
[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.
