---
tag: 0R9F850CTH
kind: statement
role: theorem
name: Gcd of Fibonacci numbers
msc: [11B39]
uses: [0GA9K57A39]
sources:
  - url: https://en.wikipedia.org/wiki/Fibonacci_sequence
    locator: Divisibility properties
---

## Statement

Let $m$ and $n$ be natural numbers, and let $F_k$ be the [[Fibonacci numbers|0GA9K57A39]].
Then
$$\gcd(F_m, F_n) = F_{\gcd(m, n)}.$$

## Remarks

Example: $\gcd(F_{12}, F_{18}) = \gcd(144, 2584) = 8 = F_6$.
In particular, $F_m$ divides $F_n$ when $m$ divides $n$. Consecutive Fibonacci numbers are coprime, because $\gcd(n, n+1) = 1$ and $F_1 = 1$.
The proof follows the Euclidean algorithm and uses the [[addition formula|00CN2F997Q]].

## Explanations

### L1 human

The greatest common divisor of two Fibonacci numbers is again a Fibonacci number.
To find which one, take the greatest common divisor of the two indices.