The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Fibonacci-GCD Proof

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


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 

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 

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 
Associated Topics:
High School Fibonacci Sequence/Golden Ratio
High School Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.