Results 1 to 2 of 2

Math Help - Proof about Fibonacci and Lucas numbers (GCD)

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    1

    Proof about Fibonacci and Lucas numbers (GCD)

    Hi.
    How to prove that GCD(F3k, L3k)=2? and If n dosen't divide with 3 GCD(Fn, Ln)=1
    Don't even know how to start that:/....Hope someone can help
    Ty.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    116
    Thanks
    1
    Quote Originally Posted by aurah View Post
    Hi.
    How to prove that GCD(F3k, L3k)=2? and If n dosen't divide with 3 GCD(Fn, Ln)=1
    Don't even know how to start that:/....Hope someone can help
    Ty.
    Try to show:
    a) L_n=F_{n+1}+F_{n-1}
    b) \gcd(F_n,F_{n+1})=1 for every n.

    Using these two properties you can get:
    \gcd(F_n,L_n)=\gcd(F_n,F_{n+1}+F_{n-1})=\gcd(F_n,F_n+2F_{n-1})=\gcd(F_n,2F_{n-1}. This is either 1 or 2, since Fn and F_n-1 are coprime. So you already know that the only possible values are 1 and 2.

    To show that they are equal to what you right, just nottice the pattern 0,0,1,0,0,1,.... when looking to the sequence Fn (or Ln) modulo 2.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci Numbers Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 13th 2011, 10:32 PM
  2. Induction Proof- Fibonacci Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 18th 2010, 07:28 AM
  3. fibonacci/lucas identity help
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: December 3rd 2009, 07:34 PM
  4. Proving Lucas Numbers and Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 19th 2008, 12:33 AM
  5. Fibonacci Numbers - proof.
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 25th 2007, 10:08 AM

Search Tags


/mathhelpforum @mathhelpforum