# Iterations in the Euclidean algorithm

Tags:
1. Oct 15, 2015

### Panphobia

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. Oct 15, 2015

### Ray Vickson

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

3. Oct 15, 2015

### Panphobia

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

4. Oct 20, 2015

### Panphobia

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

5. Oct 20, 2015

### Ray Vickson

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

6. Oct 20, 2015

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