Iterations in the Euclidean algorithm

[Panphobia]

Homework Statement

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.

The Attempt at a Solution

[/B]
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.

 

[Ray Vickson]

Homework Statement

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.

The Attempt at a Solution

[/B]
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.

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.)

 

[Panphobia]

It should be changed to ## min(m, n) \leq 2^k ##

 

[Panphobia]

To show that ## r_{k+2} \leq \frac{r_k}{2} ## how would I do that? Contradiction? Cases?

 

[Ray Vickson]

To show that ## r_{k+2} \leq \frac{r_k}{2} ## how would I do that? Contradiction? Cases?

What makes you think you need to show that? Was it supplied as a hint by the person setting the question?

 

[Panphobia]

Yeah it was supplied as a hint. According to the hint it's supposed be proven using cases. But I can't see it.