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

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

Fibonacci Numbers

Golden Ratio in Geometry

71534435