Fibonacci GCD’s, please

Fibonacci numbers exhibit striking patterns. Here’s one that may not be so obvious, but is striking when you see it. Recall the Fibonacci numbers:

 n: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,  12,  13,  14, … 
fn: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …

Now let’s look at some of their greatest common divisors

(gcd’s): gcd(f10, f7) = gcd(55, 13) = 1 = f1
gcd(f6, f9) = gcd(8, 34) = 2 = f3
gcd(f6, f12) = gcd(8, 144) = 8 = f6
gcd(f7, f14) = gcd(13, 377) = 13 = f7
gcd(f10, f12) = gcd(55, 144) = 1 = f2

Do you see the pattern? The greatest common divisor of any two Fibonacci numbers is also a Fibonacci number! Which one? If you look even closer, you’ll see the amazing general result:

gcd(fm, fn) = fgcd(m, n).

Presentation Suggestions:
After presenting the general result, go back to the examples to verify that it holds. You may wish to prepare a transparency beforehand with a table of Fibonacci numbers on it, so you can refer to it throughout the presentation.

The Math Behind the Fact:
The proof is based on the following lemmas which are interesting in their own right. All can be proved by induction. 
a) gcd(fn, fn-1) = 1, for all n 
b) fm+n = fm+1 fn + fm fn-1 
c) if m divides n, then fm divides fn 

and the ever important Euclidean Algorithm which states: if n= qm + r, then gcd(n, m) = gcd(m, r). For such n,m we have

gcd(fm, fn) = gcd(fm, fqm+r) = gcd(fm, fqm+1fr + fqmfr-1) = gcd(fm, fqm+1fr) = gcd(fm, fr)

where the 2nd equality follows from (b), the 3rd equality from (c) noting that m divides qm, and the 4th equality from noting that fm divides fqm which is relatively prime to fqm+1. Thus

gcd(fn, fm) = gcd(fm, fr)

which looks a lot like the Euclidean algorithm but with f’s on top! For example since

gcd(100, 80) = gcd(80, 20) = gcd(20, 0) = 20, then
gcd(f100, f80) = gcd(f80, f20) = gcd(f20, f0 = 0) = f20.

How to Cite this Page: 
Su, Francis E., et al. “Fibonacci GCD’s, please.” Math Fun Facts. <https://www.math.hmc.edu/funfacts>.

Fun Fact suggested by:
Arthur Benjamin

Did you like this Fun Fact?

Click to rate it.

Average rating 4.4 / 5. Vote count: 47

No votes so far! Be the first to rate this Fun Fact

Share: