Results 1 to 2 of 2

Thread: Fibonacci/Euclidean Algorithmn proof

  1. November 7th 2007, 12:48 PM #1
    padsinseven
    padsinseven is offline
    Junior Member
    Joined
    Oct 2007
    Posts
    37
    Awards
    1
    MHF Donor

    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. November 7th 2007, 04:17 PM #2
    ThePerfectHacker
    ThePerfectHacker is offline
    Global Moderator ThePerfectHacker's Avatar
    Joined
    Nov 2005
    From
    New York City
    Posts
    10,603
    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+
« Mobius Transformations | Nice Sylow Problem »

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, 12:38 PM
  2. Fibonacci Proof II
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 16th 2011, 03:04 AM
  3. Fibonacci Proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 5th 2011, 02:47 AM
  4. Euclidean Proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 2nd 2009, 09:43 PM
  5. non-Euclidean -help on proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: July 15th 2006, 06:24 PM

Search Tags


/mathhelpforum @mathhelpforum