Results 1 to 4 of 4

Math Help - Relatively prime and fibonacci

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    6

    Relatively prime and fibonacci

    Let integers a,b>0, F(i) denotes the ith Fibonacci number, such as f(1)=1, f(3)=2...
    Prove that if a and b are natural number with gcd(a,b)=1, then that gcd(F(a),F(b))=1 too
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by zhushp View Post
    Let integers a,b>0, F(i) denotes the ith Fibonacci number, such as f(1)=1, f(3)=2...
    Prove that if a and b are natural number with gcd(a,b)=1, then that gcd(F(a),F(b))=1 too

    Hint: if n|F(a) and n|F(b) then n|F(gcd(a,b))
    Can you prove this? Then the above is a corollary of this
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    6
    Quote Originally Posted by aman_cc View Post
    Hint: if n|F(a) and n|F(b) then n|F(gcd(a,b))
    Can you prove this? Then the above is a corollary of this
    Sorry, i cannot figure this out~
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Apr 2009
    Posts
    678
    Thanks
    1
    Quote Originally Posted by zhushp View Post
    Sorry, i cannot figure this out~
    Hint:
    1. Let x be the smallest number such that n|F(x)
    2. Show n|F(a) IFF x|a, for any a.
    3. Thus, in our case, x|a and x|b => x|gcd(a,b) => n|F(gcd(a,b))

    So the critical step is step 2. Work it out. Try with few examples first you will get an idea as to what's happening. Then generalize it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 01:37 PM
  2. Replies: 1
    Last Post: June 19th 2011, 01:56 PM
  3. Replies: 2
    Last Post: May 4th 2011, 03:02 PM
  4. Replies: 3
    Last Post: February 17th 2011, 08:51 AM
  5. Replies: 6
    Last Post: August 28th 2010, 12:44 AM

Search Tags


/mathhelpforum @mathhelpforum