Results 1 to 6 of 6

Math Help - Prove that the gcd of two consecutive Fibonacci numbers is 1.

  1. #1
    Junior Member
    Joined
    Jun 2008
    Posts
    54

    Prove that the gcd of two consecutive Fibonacci numbers is 1.

    Prove that the gcd of two consecutive Finonacci numbers is 1.

    Also identify the ratio F_{n+1}/F_n of consecutive Fibonacci numbers and try to identify the limit.
    Last edited by mathwizard; June 21st 2008 at 07:31 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by mathwizard View Post
    Prove that the gcd of two consecutive Finonacci numbers is 1.
    By definition, F_{n+1} = F_n + F_{n-1}.

    Assume the (F_{n+1},F_n) = d. This implies d|F_{n+1}, d|F_n and thus d|F_{n-1}. We can thus recursively(or reverse inductively) claim that d|F_n \Rightarrow d|F_{n-1}. Proceeding until n=2, we find that our hypothesis implies d|F_2,d|F_1 = 1 \Rightarrow d|1 \Rightarrow d=1

    Thus (F_{n+1},F_n) = 1 for all positive integers n.

    Quote Originally Posted by mathwizard View Post
    Also identity the ratio F_{n+1}/F_n of consecutive Fibonacci numbers and try to identity the limit.
    By definition, F_{n+1} = F_n + F_{n-1}

    If you prove that the limit exists, finding it can be easy.

    So by definition, \frac{F_{n+1}}{F_n} = 1 + \frac{F_{n-1}}{F_n} .

    Let the limit of the ratio be L, then \lim_{n \to \infty} \frac{F_{n+1}}{F_n} = \lim_{n \to \infty} \frac{F_{n}}{F_{n-1}} = L

    So \frac{F_{n+1}}{F_n} = 1 + \frac{F_{n-1}}{F_n} \Rightarrow L = 1 + \frac1{L}.

    So solve the quadratic and choose the appropriate root.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by mathwizard View Post
    Prove that the gcd of two consecutive Finonacci numbers is 1.
    We can prove something really shocking. Let F_n denote the n-th Fibonnaci number. We will prove \gcd (F_n, F_m) = F_{\gcd(n,m)}. WLOG say m\geq n. Let us apply the Euclidean algorithm to get,
    \left\{ \begin{array}{c} m = q_1n + r_1 \\ n = q_2 r_1+r_2 \\ r_1 = q_3 r_2 + r_3 \\  ... \\ r_{k-2} = q_k r_{k-1} + r_k \\ r_{k-1} = q_{k+2}r_k + 0 \end{array} \right.
    The Euclidean algorithm tells us that if a = qb + r then \gcd(a,b) = \gcd(b,r). It turns out (we will prove this soon) that we have a similar situation with Fibonacci numbers, i.e. \gcd(F_a,F_b) = F(F_b,F_r). If we assume this fact for now than: \gcd(F_n,F_m) = \gcd( F_{r_1}, F_n) = ... = \gcd(F_{r_{k-1}},F_{r_k}). Thus, the problem reduces to computing \gcd (F_{r_{k-1}},F_{r_k}). This ends up being (we will show this soon) equal to F_{r_k} which is in fact F_{\gcd(n,m)} by the Euclidean algorithm.

    To establish the above facts that we used we need an identity. This identity is F_{m+n} = F_{m-1}F_n+F_mF_{n+1} for m\geq 2. This is established by using basic induction. With this identity we can prove that if n,m\geq 1 then F_n|F_{nm}. This is proven by induction as well: the inductive step is to note F_{n(k+1)} = F_{nk+n}= F_{nk-1}F_n+F_{nk}F_{n+1} and now use induction.

    We are now in the position to prove if a=qb+r then \gcd(F_a,F_b) = \gcd(F_b,F_r) (note the fact that \gcd(F_{r_{k-1}},F_{r_k}) = F_{r_k} will follow since r_k | r_{k-1}). By identity we have \gcd(F_a,F_b) =\gcd(F_{qb+r},F_b) = \gcd(F_{qb-1}F_r+F_{qb}F_{r+1},F_b). But since b|qb we know (from above paragraph) that F_b | F_{qb}. Therefore, \gcd(F_{qb-1}F_r+F_{qb}F_{r+1},F_b) = \gcd(F_{qb-1}F_r,F_b). If we can show that \gcd(F_{qb-1},F_b)=1 then it will mean that \gcd(F_{qb-1}F_r,F_b) = \gcd(F_r,F_b). Thus, problem is reduced to proving \gcd(F_{qb-1},F_b)=1. Let d=\gcd(F_{qb-1},F_b). Since d|F_b and F_b|F_{qb} (from above) it means d|F_{qb}. But then it means d|F_{qb-1} and d|F_{qb}. It means d=1 since \gcd(F_{qb-1},F_{qb})=1 as Isomorphism showed.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Reckoner's Avatar
    Joined
    May 2008
    From
    Baltimore, MD (USA)
    Posts
    1,024
    Thanks
    75
    Awards
    1

    Smile

    Quote Originally Posted by ThePerfectHacker View Post
    We can prove something really shocking. Let F_n denote the n-th Fibonnaci number. We will prove \gcd (F_n, F_m) = F_{\gcd(n,m)}.
    Good show, TPH! That is really a beautiful result.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    this is not related to mathwizard's question, but, i hope, some memebrs find it interesting. anyway ... my apologies for posting

    something off-topic!


    i think the most fascinating fact about Fibonacci sequence is that it's periodic modulo any n \geq 2. for example Fibonacci sequence

    modulo 3 becomes: 1,1,2,0,2,2,1,0,1,1,2,0,2,2,1,0, ... \ . here 1,1,2,0,2,2,1,0 repeats in the sequence. so the period is 8.

    as far as i know finding a general formula for the period of Fibonacci sequence modulo a given number n is an open problem!!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by mathwizard View Post
    Also identify the ratio F_{n+1}/F_n of consecutive Fibonacci numbers and try to identify the limit.
    Consider the equation x^2=x+1. There are two solutions, \phi = \tfrac{1}{2}(1+\sqrt{5}) and \theta = \tfrac{1}{2}(1-\sqrt{5}). This means, \phi^2 = \phi + 1. Multiply by \phi to get \phi^3 = \phi^2 + \phi = (\phi+1)+\phi=2\phi+1. Multiply again to get, \phi^4 = 2\phi^2 + \phi = 2(\phi+1)+\phi = 3\pi+2. Do it again, \phi^5 = 5\pi +3. The pattern should be clear, \phi^n = F_n \phi+F_{n-1}. This can of course be fully justified with induction. Likewise, doing it with \theta we get \theta^n = F_n \theta + F_{n-1}. Subtracting the two equations we get \phi^n - \theta^n = F_n ( \phi - \theta). Thus, F_n = \tfrac{1}{\sqrt{5}}\left[ (\tfrac{1+\sqrt{5}}{2})^n - (\tfrac{1-\sqrt{5}}{2})^n \right]. Therefore, \tfrac{F_{n+1}}{F_n} = \tfrac{(1+\sqrt{5})^{n+1} - (1-\sqrt{5})^{n+1}}{2(1+\sqrt{5})^n - 2(1-\sqrt{5})^n}. This gives us a formula for computing the Fibonacci ratio.

    This is Mine 1th Post!!! And my 1th Celebration!!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Prove: each square is the sum of 2 consecutive triangular numbers
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: October 2nd 2010, 03:13 PM
  2. Replies: 3
    Last Post: September 23rd 2009, 01:04 PM
  3. Replies: 2
    Last Post: April 30th 2009, 07:28 AM
  4. Proving Lucas Numbers and Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 19th 2008, 12:33 AM
  5. Consecutive numbers
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: September 24th 2006, 04:57 PM

Search Tags


/mathhelpforum @mathhelpforum