Associated Topics || Dr. Math Home || Search Dr. Math

Fibonacci-GCD Proof

```Date: 11/20/2002 at 00:06:14
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,

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search