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,...
f_{n}: 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(f_{10},f_{7})
= gcd(55, 13) = 1 = f_{1}
gcd(f_{6},f_{9})
= gcd(8, 34) = 2 = f_{3}
gcd(f_{6},f_{12})
= gcd(8, 144) = 8 = f_{6}
gcd(f_{7},f_{14})
= gcd(13, 377) = 13 = f_{7}
gcd(f_{10},f_{12})
= gcd(55, 144) = 1 = f_{2}
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(f_{m},f_{n}) = f_{gcd(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(f_{n}, f_{n1}) = 1, for all n
b) f_{m+n}
= f_{m+1} f_{n}
+ f_{m} f_{n1}
c) if m divides n, then f_{m}
divides f_{n}
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(f_{m},f_{n})
= gcd(f_{m},f_{qm+r})
= gcd(f_{m},f_{qm+1}f_{r}+f_{qm}f_{r1})
= gcd(f_{m},f_{qm+1}f_{r})
= gcd(f_{m},f_{r})
where the 2nd equality follows from (b),
the 3rd equality from (c) noting that m divides qm,
and the 4th equality from noting that
f_{m} divides f_{qm}
which is relatively prime to f_{qm+1}.
Thus
gcd(f_{n},f_{m})=gcd(f_{m},f_{r})
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(f_{100},f_{80})=gcd(f_{80},f_{20})=gcd(f_{20},f_{0}=0)=f_{20}.
How to Cite this Page:
Su, Francis E., et al. "Fibonacci GCD's, please."
Math Fun Facts.
<http://www.math.hmc.edu/funfacts>.

