Math Fun Facts!
hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su
Subscribe to our RSS feed   or follow us on Twitter.
Get a random Fun Fact!
No subject limitations
Search only in selected subjects
    Calculus or Analysis
    Number Theory
    Other subjects
  Select Difficulty  
Enter keywords 

  The Math Fun Facts App!
  List All : List Recent : List Popular
  About Math Fun Facts / How to Use
  Contributors / Fun Facts Home
© 1999-2010 by Francis Edward Su
All rights reserved.

From the Fun Fact files, here is a Fun Fact at the Medium level:

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

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. <>.

Keywords:    number theory, greatest common divisor
Subjects:    number theory
Level:    Medium
Fun Fact suggested by:   Arthur Benjamin
Suggestions? Use this form.
Click to rate this Fun Fact...
    *   Awesome! I totally dig it!
    *   Fun enough to tell a friend!
    *   Mildly interesting
    *   Not really noteworthy
and see the most popular Facts!
New: get the MathFeed iPhone App!

Brings you news and views on math:
showcasing its power, beauty, and humanity

Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College!