 Solution

The Euclidean algorithm and the Fibonacci number recurrence giveIterating reaches $\gcd (F_1,F_0)=\gcd (1,0)=1$, so consecutive Fibonacci numbers are coprime.

Prove the Fibonacci addition formula by mathematical induction on $k$, asserting it simultaneously for every $n\ge 0$. At $k=1$, $F_1{F}_{n+1}+F_0{F}_n=F_{n+1}$. Suppose the formula holds at $k$. Apply it with $n+1$ in place of $n$ and use the recurrence:ThusFor $n\ge 1$, prove $F_n\mid F_{nl}$ by induction on $l$. The case $l=1$ is immediate. For $l\ge 2$, put $k=(l-1)n$ in the addition formula. Its first term is divisible by $F_n$ by the induction hypothesis, and its second term has an explicit factor $F_n$. ThereforeWhen $m>n\ge 1$, put $k=m-n$. Reducing the addition formula modulo $F_n$ gives $F_m\equiv F_{m-n}{F}_{n+1}$. Since $F_{n+1}$ is coprime to $F_n$, multiplication by it leaves the greatest common divisor with $F_n$ unchanged: any divisor of $F_n$ dividing the product divides $F_{m-n}$, by the Bezout identity or the Euclid lemma. This proves the Fibonacci gcd reductionAt $m=n$ both sides equal $F_n$, since $F_0=0$. The case $n=0$ is also immediate from $\gcd (a,0)=|a|$; the divisibility statement at $n=0$ reads $0\mid 0$, valid under the usual definition $b\mid a$ iff $a=bc$ for an integer $c$.