# Thread: [SOLVED] Greatest Common Divisor

1. ## [SOLVED] Greatest Common Divisor

What can you say about the GCD of consecutive Fibonacci numbers in the
case where we modify the initial condition and set F0 = a, F1 = b, for some
natural numbers a, b?

All I understand from this is that if F0=a then a=b=1 since F0=F1=1. What else could I saw about this ?

2. Hi

Is the fibonacci sequence defined by $f_0,\ f_1\ \text{and}\ \forall n\in\mathbb{N}\ f_{n+2}=f_{n+1}+f_n$ ?

Note that $\delta:=gcd(f_{n+2},f_{n+1})=gcd(f_{n+1}+f_n,f_n),$ so $\delta$ divides $\gamma:=gcd(f_{n+1},f_n)$ (prove it).

Conversely, $\gamma$ divides $f_n$ and $f_{n+1}$ therefore divides $f_n+f_{n+1}=f_{n+2}$ and as a consequence divides $\delta$. We're dealing with natural integers so $\gamma=\delta$.

Thus all two consecutive Fibonacci numbers have the same $gcd,$ which is $gcd(f_0,f_1)=gcd(a,b).$

Is this right?

3. Originally Posted by ronaldo_07
What can you say about the GCD of consecutive Fibonacci numbers in the
case where we modify the initial condition and set F0 = a, F1 = b, for some
natural numbers a, b?

All I understand from this is that if F0=a then a=b=1 since F0=F1=1. What else could I saw about this ?
There is a nice identity that says $\gcd(f_a,f_b) = f_{\gcd(a,b)}$.
For a proof see this.