How to find $\gcd(f_{n+1}, f_{n+2})$ by using Euclidean algorithm for the Fibonacci numbers whenever $n>1$? Find $\gcd(f_{n+1}, f_{n+2})$ by using Euclidean algorithm for the Fibonacci numbers whenever $n>1$.  How many division algorithms are needed? (Recall that the Fibonacci sequence $(f_n)$ is defined by setting $f_1=f_2=1$ and $f_{n+2}=f_{n+1}+f_n$ for all $n \in \mathbb N^*$, and look here to get information about Euclidean algorithm)

anon's answer:
$$ \gcd(F_{n+1},F_{n+2}) = \gcd(F_{n+1},F_{n+2}-F_{n+1}) = \gcd(F_{n+1},F_n). $$
Therefore
$$ \gcd(F_{n+1},F_n) = \gcd(F_2,F_1) = \gcd(1,1) = 1. $$
In other words, any two adjacent Fibonacci numbers are relatively prime.
Since
$$\gcd(F_n,F_{n+2}) = \gcd(F_n,F_{n+1}+F_n) = \gcd(F_n,F_{n+1}), $$
this is also true for any two Fibonacci numbers of distance $2$. Since $(F_3,F_6) = (2,8)=2$, the pattern ends here - or so you might think...
It is not difficult to prove that
$$F_{n+k+1} = F_{k+1}F_{n+1} + F_kF_n. $$
Therefore
$$ \gcd(F_{n+k+1},F_{n+1}) = \gcd(F_kF_n,F_{n+1}) = \gcd(F_k,F_{n+1}). $$
Considering what happened, we deduce
$$ (F_a,F_b) = F_{(a,b)}. $$
