# For Fibonacci numbers: $\gcd(F_m, F_n) = F_{\gcd(m, n)}$ [duplicate]

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!

• 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 – tatan Sep 21 '18 at 4:03
• @Le Cool! If you have done yourself, u have mastered a good amount of identities which contains Fibonacci numbers. – tarit goswami Sep 22 '18 at 19:33

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$$.