I'm working on a proof that $$\gcd(Fn, Fn-1) = 1$$ for all n greater than or equal to 0.
Here's what I have so far.
I used a proof by induction. I used $$\gcd(1,0) = 1 $$ for the base case.
For the inductive step I assumed
$$\gcd(F_n, F_{n-1}) = 1$$
and set up $$\gcd(F_{n+1}, F_n)$$ $$ = \gcd(F_n, F_{n+1} \bmod Fn)$$ $$ = \gcd(F_n, (F_n + F_{n-1]) \bmod Fn)$$
I'm a bit confused about what to do at this step. Do I use $$\gcd(a+b, b) = \gcd(a,b)$$? If so, how do I prove that? Would appreciate some help!