Results 1 to 2 of 2

Math Help - Fibonacci/Euclidean Algorithmn proof

  1. #1
    Junior Member
    Joined
    Oct 2007
    Posts
    37
    Awards
    1

    Fibonacci/Euclidean Algorithmn proof

    Let u sub n be the nth Fibonacci number. Prove that the Euclidean algorithm takes precisely n steps to prove that gcd(u sub n+1, u sub n)=1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    u_{n+1} = 1\cdot u_n + u_{n-1}
    u_{n} = 1\cdot u_{n-1}+u_{n-2}
    ...

    Keep on going until you reach the final step.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Alogritm and Fibonacci proof problem
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 29th 2012, 01:38 PM
  2. Fibonacci Proof II
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 16th 2011, 04:04 AM
  3. Fibonacci Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 5th 2011, 03:47 AM
  4. Euclidean Proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 2nd 2009, 10:43 PM
  5. non-Euclidean -help on proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: July 15th 2006, 07:24 PM

Search Tags


/mathhelpforum @mathhelpforum