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