# 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!

## marked as duplicate by Bill Dubuque elementary-number-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Aug 27 at 20:19

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