Results 1 to 3 of 3

Math Help - [SOLVED] Greatest Common Divisor

  1. #1
    Member ronaldo_07's Avatar
    Joined
    Nov 2008
    Posts
    175

    [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 ?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by ronaldo_07 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 05:45 AM
  2. Greatest Common Divisor.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 23rd 2009, 12:36 AM
  3. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 17th 2009, 07:16 PM
  4. [SOLVED] Greatest Common Divisor Problems
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 3rd 2009, 09:26 AM
  5. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 4th 2008, 01:08 AM

Search Tags


/mathhelpforum @mathhelpforum