Let $(F_n\mid n\in\Bbb N)$ be the Fibonacci sequence. Then $\gcd(F_m, F_n) = F_{\gcd(m, n)}$ for all $m,n\in\Bbb N$.

My attempt:

Lemma 1: $m\mid n\implies F_m\mid F_n$ (A user presented a proof here)

Lemma 2: $F_{m+n}=F_{m-1}F_n+F_mF_{n+1}$ (I presented a proof here)

Let $g=\gcd(m,n)$ and $d$ be any common divisor of $F_m,F_n$. From the definition of Greatest Common Divisor, it's clear that $$\gcd(F_m, F_n) = F_{\gcd(n, m)}=F_g\iff\begin{cases} F_g\mid F_m\text{ and } F_g\mid F_n\\d\space\space\mid F_g\end{cases}$$

  1. $F_g\mid F_m\text{ and } F_g\mid F_n$

Since $g=\gcd(m,n)$, $g\mid m$ and $g\mid n$. From Lemma 1, we have $$g\mid m\Rightarrow F_g\mid F_m\quad\hbox{and}\quad g\mid n\Rightarrow F_g\mid F_n$$.

  1. $d\mid F_g$

From Bézout's identity, there exists $x,y\in\mathbb Z$ such that $g=mx+ny$.

$F_m\mid F_{mx}$ [By Lemma 1] and $d\mid F_m\implies d\mid F_{mx}$. Similarly, $d\mid F_{ny}$. Thus $d\mid F_{mx-1}F_{ny}+F_{mx}F_{ny+1}$, and consequently $d\mid F_{mx+ny}$ by Lemma 2. Hence $d\mid F_g$.

Does this proof look fine or contain gaps? Do you have suggestions? Many thanks for your dedicated help!

  • 1
    $\begingroup$ It looks fine to me. You can look up the properties of Fibonacci numbers and their proofs in the following paper: whitman.edu/Documents/Academics/Mathematics/clancy.pdf $\endgroup$ – tatan Sep 21 '18 at 4:03
  • $\begingroup$ @Le Cool! If you have done yourself, u have mastered a good amount of identities which contains Fibonacci numbers. $\endgroup$ – tarit goswami Sep 22 '18 at 19:33

I find it really fine, apart for a small detail, which you maybe have clear in your mind.

In the last part, $mx$ and/or $ny$ may be negative since the Bézout coefficients $x$ and $y$ are integer numbers. You should prove that there exist $x,y\in \mathbb{N}$ such that $mx+ny=g$.


Not the answer you're looking for? Browse other questions tagged or ask your own question.