Proof by induction that fibonacci sequence are coprime

Question

I have a bit difficulty to proofe that two consecutive numbers are coprime. I have the following

The property $P(n)$ is the equation $(F_{n+1},F_n)=1$ where F_i the sequence of fibonacci is and $n \in \mathbb {N}$.

Induction hypothesis: $gcd(F_{n+1},F_n)=1$

$P(0)$ is true because $F_1=1, F_0=1$ and $gcd(1,1)=1$

To show: $gcd(F_{n+2},F_{n+1})=1$

Proof:

Fibonacci formula says

$F_{n+2}=F_{n+1}+F_n$

This is as faar as I got. How can I now get to $gcd(F_{n+2},F_{n+1})=gcd(F_{n+1},F_n)$ which would then proofe it?

Answer 1

$\gcd(F_{n+1},F_{n+2}) = \gcd(F_{n+1},F_{n+1}+F_n) = \gcd(F_{n+1},F_n)$

By the induction hypothesis $\gcd(F_{n+1},F_n)=1$ so $\gcd(F_{n+1},F_{n+2})=1$

To prove $\gcd(a,b) = \gcd(a,b-a)$ use the fact that if $c\vert a$ and $c\vert b$ then $c\vert na+mb$