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?
Best Answer
$\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$