Greatest common divisor of Fibonnacci numbers

Euclidean algorithm: If $a = bt + r$ , for integers $t$ and $r$ , then $\gcd(a, b) = \gcd(b, r)$ .

By Euclidean algorithm, we deduce that $f_n$ and $f_{n+1}$ are coprime integers, using induction: $f_{n+1} = f_n * 1 + f_{n-1} \Rightarrow \gcd (f_{n+1}, f_n) = \gcd (f_n, f_{n-1}) = \gcd ( f_{n-1}, f_{n-2}) = ... = \gcd (f_2, f_1) = 1$ .

By Binet formula for Fibonacci numbers, we deduce that $f_{m+n} = f_m * f_{n+1} + f_n * f_{m-1}$

By those two lemmas, we deduce that: \begin{array}{l l l} \gcd(f_m, f_{m+n}) & = \gcd(f_m; f_m * f_{n+1} + f_n * f_{m-1}) & \mbox{(binet formula)} \\ & = \gcd(f_m; f_n * f_{m-1}) & \mbox{ (euclidean algorithm)} \\ & = \gcd(f_m; f_n) & \mbox{(since f_m and f_{m-1} are coprime)}\\ \end{array}

We can continue reducing the indices until we reach $\gcd(f_i;f_i)$ (proceed and we get f_0). Now we can declare that $\gcd(f_m; f_n) = f_i$ , and by the way we reduced the indices, we can conclude that $i = \gcd(m,n)$ . Hence, $\gcd(f_m; f_n) = f_{\gcd(m,n)}$ , so

$\gcd (f_{484}; f_{2013}) = f_{\gcd(484 ;2013)} = f_{11} = 89$ .

[Latex edits]

An interesting property of Fibonacci Numbers is that: $\mbox{gcd}(a_{m},a_{n})=a_{\text{gcd}(m,n)}$ .
Here $a_{n}$ denotes ${n^{th} }$ Fibonacci Number.
It's proof is based on four lemmas
*Lemma 1: * For integers $n,m$ , $\mbox{gcd}(m, n) = \mbox{gcd}(m, n\pm m)$ .
This because any common factor of $n,m$ is also a factor of $n\pm m$
*Lemma 2: * For $n\gt 0$ , $\mbox{gcd}(a_{n}, a_{n-1}) = 1$
In other words, any two consecutive Fibonacci numbers are mutually prime. It can be easily proved by induction and Lemma 1.
*Lemma 3: * Assume, $\mbox{gcd}(m,n)=1$ , then $\mbox{gcd}(m,nk)=\mbox{gcd}(n,k)$ .
This is because any mutual factor of $m$ and $nk$ divides $k$ , because it can't divide $n$ .
*Lemma 4: * $a_{m+n} = a_{m}a_{n+1} + a_{m-1}a_{n}.$ . For its proof visit here

Now proving the main proposition:

Let then $n = mk + r$ , $0 \le r \lt m$ . We have

$\begin{array}{rll} \mbox{gcd}(a_{m},a_{n}) &= \mbox{gcd}(a_{mk+1}a_{r}+a_{mk}a_{r-1}) & \space due \space to \space \mbox{Lemma} \space 4 \\ &=\mbox{gcd}(a_{m},a_{mk+1}a_{r}) & \space because \space a_m|a_{mk} \\ &=\mbox{gcd}(a_{m},a_{r}) & \space due \space to \space \mbox{Lemma} \space 3. \end{array}$

If we lose the functional symbol $a_{}$ , the subscripts form a step in Euclid's algorithm. As there, the process can continue until the remainder $r$ becomes zero. At this step we claim that the previous (the last non-zero) remainder is exactly the greatest common divisor of the two original numbers. What we showed so far is that applying Euclid's algorithm to $a_m$ and $a_n$ goes exactly in parallel with applying it to the subscripts. So when eventually we arrive at, say, $\mbox{gcd}(m,n)=\mbox{gcd}(s,0)$ , and declare that $\mbox{gcd}(m,n)=s$ , we can at the same time to declare that $\mbox{gcd}(a_{m},a_{n})=\mbox{gcd}(a_{s},0)$ and, hence, that $\mbox{gcd}(a_{m},a_{n})=\mbox{gcd}(a_{s},0)=a_{s}=a_{\text{gcd}(m,n)}$ .

Now the problem is to find $\mbox{gcd}(a_{484},a_{2013})$ which will be equal to $a_{\text{gcd}(484,2013)} = a_{11} = 89$

Observe the recursion formula: $a_{n} = a_{n-1}+a_{n-2} = 2a_{n-2}+a_{n-3} = 3a_{n-3}+2a_{n-4}$ $= \cdots = a_{m+1}a_{n-m}+a_{m}a_{n-m-1}$ ----(1)

Let $(a,b)$ means the greatest common divisor of $a$ and $b$ .

$(a_{n}, a_{n+1}) = (a_{n+1}-a_{n}, a_{n}) = (a_{n-1}, a_{n}) = \cdots = (a_{1}, a_{2}) = (1, 1) = 1$ Therefore, the consecutive terms are coprime numbers.

By (1), $a_{2013} = a_{1530}a_{484} + a_{1529}a_{483}$

By Euclidean algorithm, $(a_{484}, a_{2013}) = (a_{484}, a_{1529}a_{483}) = (a_{484}, a_{1529})$

( $\because$ $a_{483}$ and $a_{484}$ are coprime numbers as we showed it.)

By watching this process carefully, we can understand that $(a_{B}, a_{A}) = (a_{B}, a_{r})$ provided that $A \geq B$ and $r$ is the remainder when $A$ is divided by $B$ .

Apply this in calculation: $(a_{484}, a_{2013}) = (a_{484}, a_{77}) = (a_{22}, a_{77}) = (a_{22}, a_{11}) = a_{11}= 89$

cf. In the algorithm, we can define $a_{0} = 0$ .

GCD of two fibonacci numbers is simply the fibonacci number of GCD of that two numbers.. i.e. GCD of Fn and Fm will be F(gcd of m and n). Gcd of 484 and 2013 is 11. Hence ans is F11 = 89.

Because the Fibonacci Sequence satisfies $gcd(F_m,F_n) = F_{\gcd(m,n)}$ then we need only find the greatest common divisor of 484 and 2013. Looking at the prime factorizations:

$2013=3*11*61$

$484=2*2*11*11$

We can find the greatest common divisor by listing all the prime factors they have in common. In this case the only prime factor they have in common is 11.

That does not mean the gcd of the two terms is 11, but that $F_{11}$ will be our gcd.

After making a short list of the Fibonacci Sequence:

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

We see that 89 will be our greatest common divisor.

The Fibonacci Sequence is an example of Divisibility Sequence

Thus,

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

We have to find $gcd (a_{484},a_{2013})$ which is same as $a_{gcd(484,2013)}$

So, $gcd(484,2013)=11$ .

Now we have to find $a_{11}$ which is the answer to our question.

$a_{11}$ can be easily calculated out as $89$ .

Hence $gcd (a_{484},a_{2013})$ = $89$

So that we can find the desired value, we must use the following formula:

$\text{GCD} (a_{m},a_n) = a_{\text{GCD}(m,n)},$ which was tested in 1876 by ​​the mathematician F. Edouard. A. Lucas (a demonstration (in portuguese) is in the 2.5 section of here , whence we have:

$\text{GCD}(a_{2013},a_{484}) = a_{\text{GCD}(2013,484)}$

Let's calculate the $\text{GCD}(2013,484),$ for this, we'll use the Euclidean Algorithm:

$\\ \text{GCD}(2013,484) = \text{GCD}(2013-4 \cdot 484,484) \\ = \text{GCD}(77,484) = \text{GCD}(77,484-6 \cdot 77) \\ = \text{GCD}(77,22) = 11$

Whence we have $a_{\text{GCD}(2013,484)}=a_{11} = 89.$ Therefore:

$\text{GCD}(a_{2013},a_{484}) = 89$

This number (89) is the desired result.

For this question we can use the theorem $\gcd(f_{m},f_{n}) = f_{\gcd(m,n)}$

Thus the answer to this question is $\gcd(a_{484},a_{2013}) = a_{\gcd(484,2013)} = a_{11} = 89$

A well-substantiated proof of the theorem used above can be found at the link GCD of Fibonnacci numbers

The GCD of any two Fibonacci numbers $f_x$ and $f_y$ is $f_{\gcd{(f_x,f_y)}}$ . Therefore, the GCD of $f_{484}$ and $f_{2013}$ is $f_{11} = \boxed{89}$ .

Sorry for this

Let's observe the first few Fibonacci numbers.

$F_1 = 1$

$F_2 = 1$

$F_3 = 2$

$F_4 = 3$

$F_5 = 5$

$F_6 = 8$

$F_7 = 13$

$F_8 = 21$

$F_9 = 34$

$F_{10} = 55$

$F_{11} = 89$

$F_{12} = 144$

$F_{13} = 233$

$F_{14} = 377$

$\vdots$

and so on.

From the above list, I observed (but couldn't prove it properly) that $\textrm{gcd}(F_a, F_b) = F_{\textrm{gcd}(a, b)}$

So, $\textrm{gcd}(F_{484}, F_{2013}) = F_{\textrm{gcd}(484, 2013)}$

$= F_{11}$

$=\boxed{89}$

Proof : In the list of Fibonacci Numbers, we see an amazing pattern.

$F_{3}, F_{6}, F_{9}, F_{12}, \ldots F_{3n}$ are divisible by $F_{3}$ , i.e. $2$ $(n \in \mathbb{N})$

Similarly,

$F_{4}, F_{8}, F_{12}, F_{16}, \ldots F_{4n}$ are divisible by $F_{4}$ , i.e. $3$ $(n \in \mathbb{N})$

Similarly,

$F_{5}, F_{10}, F_{15}, F_{20}, \ldots F_{5n}$ are divisible by $F_{5}$ , i.e. $5$ $(n \in \mathbb{N})$

This pattern can be generalized.

$F_{k}, F_{2k}, F_{3k}, F_{4k}, \ldots$ will be divisible by $F_{k}$ $(k \in \mathbb{N})$

Now let's take any two Fibonacci numbers $F_{a}$ and $F_{b}$

The prime factorization of $a$ would be $\phantom{l}$ $2^p \cdot 3^q \cdot 5^r \ldots$

Similarly, the prime factorization of $b$ would be $\phantom{l}$ $2^x \cdot 3^y \cdot 5^z \ldots$

Suppose $\textrm{gcd}(a, b) = 2^x \cdot 3^q \cdot 5^z \ldots$ .

$F_{a}$ would be divisible with $F_{2^p}, F_{3^q}, F_{5^r} \ldots$

Similarly, $F_{b}$ would be divisible with $F_{2^x}, F_{3^y}, F_{5^z} \ldots$

Therefore $\textrm{gcd}(F_a, F_b)$ will be divisible by $F_{2^x}, F_{3^q}, F_{5^z} \ldots$

$\textrm{gcd}(F_a, F_b) = F_{2^x \cdot 3^q \cdot 5^z} \ldots$

$\textrm{gcd}(F_a, F_b) = F_{\textrm{gcd}(a, b)}$

courtesy of wikipedia: gcd( F(m), F(n) ) = F( gcd(m, n) )

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

def gcd(a, b):
    if a < b:
        spam = a
    else:
        spam = b
    while spam > 0:
        if a%spam == 0 and b%spam == 0:
            return spam
        spam -= 1
    return 1 

def fib(n):
    x = z = 0
    y = 1
    while n > 1:
        z = x+y
        x = y
        y = z
        n -= 1
    return y    

print fib(gcd(484, 2013))    

Answer: 89

Greatest common divisor formula for Fibonacci numbers are,

gcd(Fm, Fn) = F(gcd(m,n))

In this case GCD(484, 2013)=11 and 11th Fibonacci number is 89. So this is the answer.

The proof for this formula can be found here: http://www.math.hmc.edu/funfacts/ffiles/20004.5.shtml

We use the following result: For For m,n≥1, gcd(f {m},f {n})=f {gcd(m,n)} Here m=484, n=2013 gcd(484,2013)=11 f {11} = 89

$gcd(f_{m},f_{n})=f_{gcd(m,n)}.$

$gcd(484, 2013)=11$ , so the ans is $f_{11}=\boxed{89}$

$GCD(F_{m}, F_{n}) = F_{GCD(m,n)}$

$GCD(484, 2013) = 11$

$F_{11} = 89$