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(55, 13) = 1 = f1
= gcd(8, 34) = 2 = f3
= gcd(8, 144) = 8 = f6
= gcd(13, 377) = 13 = f7
= 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).
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 Math Behind the Fact:
The proof is based on the following lemmas which are
interesting in their own right. All can be proved by
a) gcd(fn, fn-1) = 1, for all n
= fm+1 fn
+ fm fn-1
c) if m divides n, then fm
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
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.
which looks a lot like the Euclidean algorithm but with f's
For example since gcd(100,80)=gcd(80,20)=gcd(20,0)=20, then
How to Cite this Page:
Su, Francis E., et al. "Fibonacci GCD's, please."
Math Fun Facts.