Fibonacci-GCD Proof

Date: 11/20/2002 at 00:06:14
From: Shyamal Upadhyaya
Subject: Fibonacci-gcd proof

Hi,

Can you help me prove

   fib(gcd(m, n)) = gcd(fib(m), fib(n))

(gcd - greatest common divisor)
(fib - fibonacci number)

I have tried to prove this using Fibonacci properties.

Help is greatly appreciated!

Date: 11/21/2002 at 05:52:32
From: Doctor Floor
Subject: Re: Fibonacci-gcd proof

Hi, Shamyal,

Thanks for your question.

First we note that fib(n) and fib(n+1) are always relatively prime. 
See, for instance, from the Dr. Math library:

   Consecutive Fibonacci Numbers Relatively Prime
   http://mathforum.org/library/drmath/view/52716.html 

Now let us consider two Fibonacci numbers fib(t) and fib(t+u). We may 
use that

   fib(t+u) = fib(t)*fib(u-1) + fib(u)*fib(t-1)

as, for instance, in the Dr. Math archives at

   Fibonacci Sequence Property
   http://mathforum.org/library/drmath/view/51624.html 

From this we see that

  gcd(fib(t), fib(t+u)) = 
  gcd(fib(t), fib(t)*fib(u-1) + fib(u)*fib(t-1)) =
  gcd(fib(t), fib(u)*fib(t-1)) =
  gcd(fib(t), fib(u))

where the latest step is justified by the fib(n) and fib(n+1) being 
relatively prime.

Now the proof of the statement fib(gcd(m, n)) = gcd(fib(m), fib(n)) 
can be completed using the Euclidean algorithm.

If you have more questions, just write back.

Best regards,
- Doctor Floor, The Math Forum
  http://mathforum.org/dr.math/