Fibonacci numbers | gcd …. (Part 2)

The gcd of any two Fibonacci numbers is also a Fibonacci number

$gcd \, (F_3, F_2) \; = \; gcd \, (3, 2) \; = \; 1 \; = \; F_1 \; = \; F_2$

$gcd \, (F_5, F_3) \; = \; gcd \, (5, 2) \; = \; 1 \; = \; F_1 \; = \; F_2$

$gcd \, (F_6, F_9) \; = \; gcd \, (8, 34) \; = \; 2 \; = \; F_3$

$gcd \, (F_6, F_{12}) \; = \; gcd \,(8,144) \; = \; 8 \; = \; F_6$

$gcd \, (F_7, F_{14}) \; = \; gcd \,(13,377) \; = \; 13 \; = \; F_7$

$gcd \, (F_m, \; F_n) \; = \; F_{gcd \,(m,n)}$

->   $gcd \, (F_n, \; F_{n-1}) \; = \; 1$   for all   $n$

->   $F_{m+n} \; = \; F_{m+1} \, F_n \; + \; F_m \, F_{n-1}$

->   if   $m$   divides   $n$,   then   $F_m$   divides   $F_n$
If   $n = qm + r$,   then   $gcd \,(n,m) \; = \; gcd \,(m,r)$
For such   $n, m$   we have

$gcd \,(F_m, \; F_n)$
$= \; gcd \,(F_m, \; F_{qm + r})$
$= \; gcd \,(F_m, \; F_{qm+1} \, F_r \; + \; F_{qm} \, F_{r-1})$
$= \; gcd \,(F_m, \; F_{qm+1} \, F_r)$
$= \; gcd \, (F_m, \; F_r)$

$gcd \,(F_m, \; F_n) \; = \; gcd \, (F_m, \; F_r)$