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_{n-1}) = 1, for all n

b) f_{m+n} = f_{m+1} f_{n} + f_{m} f_{n-1}

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_{r-1}) = 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*. <https://www.math.hmc.edu/funfacts>.

**Fun Fact suggested by:**

Arthur Benjamin