Results 1 to 4 of 4

Math Help - Euclidean algorithm

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Euclidean algorithm



    All I think can of is the following:
    Since the reaminder become strictly smaller each step, the worst case is when the remainders go down by 1 each step, in which case the process will take "b" steps in total to complete. Therefore, the process will terminate in at most "b" steps.

    But how can we prove that all reaminders satisfy the inequality r(i+2) < r(i)/2? By induction? or...? This seems to provide a much better upper bound on the number of steps to complete the process.

    Any help is much appreciated!

    [also under discussion in s.o.s. math board]
    Last edited by kingwinner; January 19th 2010 at 09:08 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Well you have r_i = r_{i+1}q_{i+2}+r_{i+2}. So r_i-2r_{i+2} = r_{i+1}q_{i+2}-r_{i+2}. Since q_{i+2}\geq 1 and 0<r_{i+1}<r_{i+2} you have r_i-2r_{i+2} = r_{i+1}q_{i+2}-r_{i+2} \geq r_{i+1}-r_{i+2} > 0.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by Bruno J. View Post
    Well you have r_i = r_{i+1}q_{i+2}+r_{i+2}. So r_i-2r_{i+2} = r_{i+1}q_{i+2}-r_{i+2}. Since q_{i+2}\geq 1 and 0<r_{i+1}<r_{i+2} you have r_i-2r_{i+2} = r_{i+1}q_{i+2}-r_{i+2} \geq r_{i+1}-r_{i+2} > 0.
    But I think q(i+2) can be 0?

    Also, I think we should have 0<r(i+2)<r(i+1)?

    thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by kingwinner View Post
    But I think q(i+2) can be 0?
    Remember, r_i \ge r_{i + 1} (if equal, the algorithm only has one step). If the algorithm starts with r_{i + 1} > r_i, then they are switched in the very next line. So, if our algorithm is to have more than one line, it is just assumed that r_i > r_{i + 1} right off the bat. In this case, q_{i + 2} \ge 1 is forced to happen.

    Also, I think we should have 0 < r_{i + 2} < r_{i + 1}?
    yes, BrunoJ had a typo. But if you look at what he did, you can see that he assumed just as you wrote here.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 30th 2010, 11:46 AM
  2. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 14th 2010, 07:53 AM
  3. [SOLVED] Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 5th 2010, 07:45 PM
  4. GCD and the Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 3rd 2010, 04:20 AM
  5. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 8th 2009, 09:28 AM

Search Tags


/mathhelpforum @mathhelpforum