Results 1 to 3 of 3

Math Help - Euclid's algorithm and fibonacci numbers

  1. #1
    Junior Member
    Joined
    Mar 2011
    Posts
    72

    Euclid's algorithm and fibonacci numbers

    Let F_{0}, F_{1}, F_{2}, F_{3},... be the Fibonacci numbers, defined by

    F_{0}=1

    F_{1}=1

    F_{n}=F_{n-1}+F_{n-2}

    for n\geq 0

    a) Prove that for all n\geq 0 we have gcd(F_{n+1}, F_{n})=1

    b) Prove that for all n\geq 0 we also have gcd(F_{n+2}, F_{n})=1

    (Check what Euclid's algorithm would do if you started to compute gcd(F_{n+1}, F_{n}) or gcd(F_{n+2}, F_{n}).)

    Any help would be greatly appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor MarkFL's Avatar
    Joined
    Dec 2011
    From
    St. Augustine, FL.
    Posts
    1,988
    Thanks
    734

    Re: Euclid's algorithm and fibonacci numbers

    a) I would use the algorithm to state:

    \gcd(F_{n+1},F_{n})=\gcd(F_{n+1}-F_{n},F_{n})=\gcd(F_{n-1},F_{n})=\gcd(F_{n},F_{n-1})

    Thus, iterating the algorithm n-1 times, we will find \gcd(F_{n+1},F_{n})=\gcd(F_2,F_1)=\gcd(1,1)=1.

    b) The first subtraction gives:

    \gcd(F_{n+2},F_{n})=\gcd(F_{n+1},F_{n}) now using the result from part a) we then find:

    \gcd(F_{n+2},F_{n})=1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2012
    From
    iran
    Posts
    2

    Re: Euclid's algorithm and fibonacci numbers

    hi
    I neead an algorithm for drawing this:
    Fibonacci Tornado mod 2
    please help!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] O(Log(n)) Algorithm for Computing Fibonacci Numbers, SICP Ex. 1.19
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 9th 2011, 10:55 AM
  2. Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 29th 2009, 04:54 AM
  3. Another GCD using Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 23rd 2008, 09:03 AM
  4. Euclid's algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 3rd 2008, 05:18 AM
  5. Euclid Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: April 10th 2008, 05:28 AM

Search Tags


/mathhelpforum @mathhelpforum