Results 1 to 4 of 4

Math Help - Euclid's algorithm question

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    13

    Euclid's algorithm question

    Let b=r_0, r_1, r_2... be the successive remainders in the Euclidean Algorithm applied to a and b. Show that r_{i+2} \le r_i/2 for all i.

    I'm thinking that this is proven by induction but I am stuck on the inductive step.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Aug 2009
    Posts
    125
    You don't need induction.
    Suppose that r_{i+2}>r_i/2

    r_{i-1} = q_ir_i+r_{i+1}
    r_i = q_{i+1}r_{i+1}+r_{i+2}

    we have r_i = q_{i+1}r_{i+1}+r_{i+2} > q_{i+1}r_{i+1} + r_i/2
    r_i/2 > q_{i+1}r_{i+1} a contradiction.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2009
    Posts
    2
    can you explain why its a contradiction
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Aug 2009
    Posts
    125
    Quote Originally Posted by ilovepurerubbish View Post
    can you explain why its a contradiction
    It contradicts the choice of q_{i+1}. Do you see that we could as well take q_{i+1}+1 instead of q_{i+1} (which contradicts the fact that we always take maximal possible q's)?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclid Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 15th 2012, 12:32 PM
  2. Help with Euclid's algorithm question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 4th 2010, 11:50 AM
  3. Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 29th 2009, 05:54 AM
  4. Another GCD using Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 23rd 2008, 10:03 AM
  5. Euclid's algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 3rd 2008, 06:18 AM

Search Tags


/mathhelpforum @mathhelpforum