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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2015 The Math Forum