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.