# 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 $\displaystyle f_0,\ f_1\ \text{and}\ \forall n\in\mathbb{N}\ f_{n+2}=f_{n+1}+f_n$ ?

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

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

Thus all two consecutive Fibonacci numbers have the same $\displaystyle gcd,$ which is $\displaystyle 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 $\displaystyle \gcd(f_a,f_b) = f_{\gcd(a,b)}$.
For a proof see this.