Remainder of Fibonacci Number Divided by Fibonacci Number is Plus or Minus Fibonacci Number
Jump to navigation
Jump to search
Theorem
Let $F_n$ and $F_m$ be Fibonacci numbers.
By the Division Theorem, let:
- $F_n = q F_m + r$
where:
- $q \in \Z$
- $r \in \Z: 0 \le r < \size {F_m}$
Then either $r$ or $\size {F_m} - r$, or both, is a Fibonacci number.
Proof
Follows directly from Residue of Fibonacci Number Modulo Fibonacci Number.
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.8$: Fibonacci Numbers: Exercise $32$