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,...
Examples:
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 equality (*) follows from (b), (**) from (c) noting
that m divides qm, and (***) 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."
Mudd Math Fun Facts.
<http://www.math.hmc.edu/funfacts>.
Bookmark this page on:
|
Digg this!
|
Del.icio.us
|
Technorati
|
Reddit
|
Fark
|
Squidoo
|
Furl
|
Blinklist
|
Yahoo MyWeb
|
Google
|
Stumbleupon
|
|
|
RSS feed to get the latest Fun Facts!
