Fibonacci numbers form a strong divisibility sequence: gcd(F_m, F_n) = F_gcd(m,n)
ProvedFamousTheorems.fibonacci_gcd_strong_divisibility_6bThe Fibonacci numbers form a strong divisibility sequence. For all natural numbers ,
where , and .
Lucas proved this in 1876. It implies that whenever , that consecutive Fibonacci numbers are coprime, and that can be prime only when is prime or . The same property holds for Lucas sequences and underlies primality tests for Mersenne numbers.
Formalization note. Mathlib's Nat.fib_gcd. Nat.fib is the Fibonacci sequence with Nat.fib 0 = 0 and Nat.fib 1 = 1.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems theorem fibonacci_gcd_strong_divisibility_6b (m n : ℕ) : Nat.fib (Nat.gcd m n) = Nat.gcd (Nat.fib m) (Nat.fib n) := by sorry end FamousTheorems
Source
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `Nat.fib_gcd`. Proof here reduces to that Mathlib result.