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!
or
No subject limitations
Search only in selected subjects
    Algebra
    Calculus or Analysis
    Combinatorics
    Geometry
    Number Theory
    Probability
    Topology
    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
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. <http://www.math.hmc.edu/funfacts>.

Share

Keywords:    number theory, greatest common divisor
Subjects:    number theory
Level:    Medium
Fun Fact suggested by:   Arthur Benjamin
Suggestions? Use this form.
4.05
 
current
rating 		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!
Get the Math Fun Facts
iPhone App!

Want another Math Fun Fact?

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