hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su

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

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

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.

Su, Francis E., et al. "Fibonacci GCD's, please." Math Fun Facts. <http://www.math.hmc.edu/funfacts>.

Keywords:    number theory, greatest common divisor
Subjects:    number theory
Level:    Medium
Fun Fact suggested by:   Arthur Benjamin
Suggestions? Use this form.
3.37
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!