Peter wrote: The Fibonacci sequence $\{F_{n}\}$ is defined by \[F_{1}=1, \; F_{2}=1, \; F_{n+2}=F_{n+1}+F_{n}.\] Show that $\gcd (F_{m}, F_{n})=F_{\gcd (m, n)}$ for all $m, n \in \mathbb{N}$. Let's use the following lemma Lemma 1: If $\{x_{n}\}_{n\ge1}$ is a sequence of real numbers defined by $x_{1}=a,x_{2}=b$ ($a,b\in{R}$) and $x_{n+2}=bx_{n+1}+ax_{n}$, then $x_{n+m}=x_{n}x_{m+1}+x_{n-1}x_{m}$ for any positive integer $m$. See the proof here: http://www.problem-solving.be/pen/viewtopic.php?p=689#689 Now we can see that Fibonacci sequence has all the condition's of the lemma,so $F_{x+y}=F_{x}F_{y+1}+F_{x-1}F_{y}$ $x,y\in{N}$ Let's suppose that $m>n$ then putting $x+y=m$ and $y=n$ we get that $F_{m}=F_{m-n}F_{n+1}+F_{m-n-1}F_{n}.$ As we have that \[\gcd(F_{n+1};F_{n})=\gcd(F_{n};F_{n-1})=...=\gcd(F_{2};F_{1})=1\] then$\gcd(F_{m};F_{n})=\gcd(F_{m};F_{m-n})$ therefore $\gcd(F_{m};F_{n})=F_{\gcd(m;n)}$

I wrote: Why does $ gcd(F_{m};F_{n}) = gcd(F_{m};F_{m-n})\implies gcd(F_{m};F_{n}) = F_{gcd(m;n)}$? Well I figured out why... and I'll post it here in case other people are confused too (as opposed to deleting this post) ________________________________________________________________________________________________ \[{ \text{gcd}(F_{m};F_{n}) =\text{gcd}(F_{m};F_{m-n})\implies\text{gcd}(F_{m};F_{\text{gcd}(m,n)}) =\text{gcd}(F_{\text{gcd}(m,n)}};F_{m-\text{gcd}(m,n)})=...=\text{gcd}(F_{\text{gcd}(m,n)};F_{\text{gcd}(m,n)})=\text{gcd}(m,n)\] Now since $ \text{gcd}\left(\frac{n}{\text{gcd}(m,n)},n\right)=1$ we deduce $ \text{gcd}(F_{m};F_{n}) = F_{\text{gcd}(m;n)}$

From the proven statement, we can prove that this $ F_{\text{gcd}(m,n)}|gcd(F_{m}.F_{n})$ but nothing else. How to continue?