Blog → Number Theory → Fibonacci Numbers

The Fibonacci sequence is one of the most famous integer sequences in mathematics. Defined by the simple recurrence

F₀ = 0, F₁ = 1, Fₙ = Fₙ₋₁ + Fₙ₋₂ for n ≥ 2

its properties intersect a surprising number of areas in number theory, from divisibility to prime testing.

Basic Properties

• Every third Fibonacci number is even: F₃k is even.
• Greatest common divisor: gcd(Fₘ, Fₙ) = F_{gcd(m,n)}.
• Identity: Fₙ₊₁ Fₙ₋₁ – Fₙ² = (‑1)ⁿ (Cassini’s identity).

Divisibility

If a prime p divides Fₙ, then the rank of apparition of p (the smallest k such that p | Fₖ) divides p – (5|p), where (5|p) is the Legendre symbol.

Fibonacci Modulo m

When the sequence is taken modulo an integer m, it becomes periodic. The length of this period is called the Pisano period, denoted π(m).

Interactive Fibonacci Calculator

Further Reading

• Knuth, The Art of Computer Programming, Vol. 1, §1.2.
• Vajda, Fibonacci & Lucas Numbers.
• Research on Pisano periods (see OEIS A001175).