GCD of Fibonacci Numbers

Elsewhere we proved that, for \(m,n\ge 1\), \(f_{m}\) divides \(f_{mn}\), where \(f_{m}\) is the Fibonacci number defined recursively with

\(f_{0}=0, f_{1}=1, f_{n+1}=f_{n}+f_{n-1}, n \ge 1.\)

We shall employ this fact to establish a stronger

Proposition

For For \(m,n\ge 1\),

\(\mbox{gcd}(f_{m},f_{n})=f_{\text{gcd}(m,n)}\).

The proof will be based on four lemmas; before stating and proving those I'd like to give an example. Doing that with wolframalpha is a snap.

Example

\(f_{34}=5702887=1597\times 3571\), \(f_{51}=20365011074=2\times 1597\times 637021\), while \(f_{\text{gcd}(34,51)}=f_{17}=1597=\mbox{gcd}(f_{34},f_{51})\).

Lemma 1

For integers \(n,m\), \(\mbox{gcd}(m, n) = \mbox{gcd}(m, n\pm m)\).

This because any common factor of \(n,m\) is also a factor of \(n\pm m\).

Lemma 2

For \(n\gt 0\), \(\mbox{gcd}(f_{n}, f_{n-1}) = 1\),

In other words, any two consecutive Fibonacci numbers are mutually prime.

The easiest proof is by induction. There is no question about the validity of the claim at the beginning of the Fibonacci sequence: \(1, 1, 2, 3, 5, \ldots\) Let for some \(k\gt 1\), \(\mbox{gcd}(f_{k},f_{k-1})=1\). Then, by Lemma 1,

\(\mbox{gcd}(f_{k},f_{k+1})=\mbox{gcd}(f_{k},f_{k}+f_{k-1})=\mbox{gcd}(f_{k},f_{k-1})=1\).

Lemma 3

Assume, \(\mbox{gcd}(m,n)=1\), then \(\mbox{gcd}(m,nk)=\mbox{gcd}(m,k)\).

This is because any mutual factor of \(m\) and \(nk\) divides \(k\), because it can't divide \(n\).

Lemma 4

\(f_{m+n} = f_{m}f_{n+1} + f_{m-1}f_{n}.\)

This has been proved elsewhere.

From Lemma 1, (or Euclid's algorithm), \(\mbox{gcd}(m,mk+r)=\mbox{gcd}(m,r)\).

Proof of Proposition

Let then \(n = mk + r\), \(0 \le r \lt m\). We have

\( \begin{array}{rll} \mbox{gcd}(f_{m},f_{n}) &= \mbox{gcd}(f_{m},f_{mk+1}f_{r}+f_{mk}f_{r-1}) & \space due \space to \space \mbox{Lemma} \space 4 \\ &=\mbox{gcd}(f_{m},f_{mk+1}f_{r}) & \space because \space f_m|f_{mk} \\ &=\mbox{gcd}(f_{m},f_{r}) & \space due \space to \space \mbox{Lemma} \space 3. \end{array} \)

If we lose the functional symbol \(f_{}\), the subscripts form a step in Euclid's algorithm. As there, the process can continue until the remainder \(r\) becomes zero. At this step we claim that the previous (the last non-zero) remainder is exactly the greatest common divisor of the two original numbers. What we showed so far is that applying Euclid's algorithm to \(f_m\) and \(f_n\) goes exactly in parallel with applying it to the subscripts. So when eventually we arrive at, say, \(\mbox{gcd}(m,n)=\mbox{gcd}(s,0)\), and declare that \(\mbox{gcd}(m,n)=s\), we can at the same time to declare that \(\mbox{gcd}(f_{m},f_{n})=\mbox{gcd}(f_{s},0)\) and, hence, that

\(\mbox{gcd}(f_{m},f_{n})=\mbox{gcd}(f_{s},0)=f_{s}=f_{\text{gcd}(m,n)}\).

Corollary

If \(f_{m}|f_{n}\) then \(m|n\).

Indeed, if \(f_{m}|f_{n}\) then \(f_{m}=\mbox{gcd}(f_{m},f_{n})\). By the proposition just proved, it follows that \(m=\mbox{gcd}(m,n)\). But this is exactly what was claimed.

References

  1. A. T. Benjamin, J. J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, MAA, 2003
  2. R. Grimaldi, Fibonacci and Catalan Numbers: an Introduction, Wiley, 2012

Fibonacci Numbers

  1. Ceva's Theorem: A Matter of Appreciation
  2. When the Counting Gets Tough, the Tough Count on Mathematics
  3. I. Sharygin's Problem of Criminal Ministers
  4. Single Pile Games
  5. Take-Away Games
  6. Number 8 Is Interesting
  7. Curry's Paradox
  8. A Problem in Checker-Jumping
  9. Fibonacci's Quickies
  10. Fibonacci Numbers in Equilateral Triangle
  11. Binet's Formula by Inducion
  12. Binet's Formula via Generating Functions
  13. Generating Functions from Recurrences
  14. Cassini's Identity
  15. Fibonacci Idendtities with Matrices
  16. GCD of Fibonacci Numbers
  17. Binet's Formula with Cosines
  18. Lame's Theorem - First Application of Fibonacci Numbers

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2017 Alexander Bogomolny

 62644872

Search by google: