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

Question

This question already has an answer here:

• Fibonacci modular results $\ F_n\mid F_{kn},\,$ $\, \gcd(F_n,F_m) = F_{\gcd(n,m)}$ 5 answers

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

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

Answer 1

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