1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Iterations in the Euclidean algorithm

Tags:
  1. Oct 15, 2015 #1
    1. The problem statement, all variables and given/known data
    Let m and n be natural numbers. Suppose ## min(m, n) \geq 2^k ## for some natural number k. Show that the Euclidean Algorithm needs at most ## 2k ## iterations to calculate the gcd of m and n.


    3. The attempt at a solution

    So far I think I need to show that for all the remainders ## r_{k} ## ## r_{k+2} \leq \frac{r_{k}}{2} ##. But I have no idea what else to do or how to prove that.
     
  2. jcsd
  3. Oct 15, 2015 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    The statement is incomplete: I think you had better say ##2^k \leq \min(m,n) < 2^{k+1}##. (Otherwise, ##k = 1## would satisfy your hypothesis, and your claim would be that for any pair ##m,n \geq 2## we can find their gcd in at most 2 steps.)
     
  4. Oct 15, 2015 #3
    It should be changed to ## min(m, n) \leq 2^k ##
     
  5. Oct 20, 2015 #4
    To show that ## r_{k+2} \leq \frac{r_k}{2} ## how would I do that? Contradiction? Cases?
     
  6. Oct 20, 2015 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    What makes you think you need to show that? Was it supplied as a hint by the person setting the question?
     
  7. Oct 20, 2015 #6
    Yeah it was supplied as a hint. According to the hint it's supposed be proven using cases. But I can't see it.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Iterations in the Euclidean algorithm
  1. Euclidean Geometry (Replies: 1)

  2. Iterative method (Replies: 3)

Loading...