Proving the number of iterations in the Euclidean algorithm

Let m and n be natural numbers. Suppose $ min(m, n) \leq 2^k $ for some natural number k. Show that the Euclidean algorithm needs at most $ 2k $ iterations to find the GCD of m and n. Basically I have no clue how to start this proof, I think I should be looking at the remainders and somehow showing that $ a_{k+2} \leq \frac{a_{k}}{2} $ where $a_{k}$ represents the kth remainder. Other than that, I have no clue about where to begin.

Solution 1:

In two steps we move from $(m,n)$ to $(m'=n,n'=m\bmod n)$ and then to $(m''=n',n''=m'\bmod n')$. Assume $n\le 2^k$. Then $m',n'\le 2^k$ and $n''\le \min\{m',n',|m'-n'|\}$. Henc $n''>2^{k-1}$ could only happen if both $|m'-n'|>2^{k-1}$ and $\min\{n',m'\}>2^{k-1}$, which implies $\max\{m',n'\}>2^{k-1}+2^{k-1}=2^k$, contradiction. Hence after two steps $n\le 2^k$ becomes $n''\le 2^{k-1}$

Hence if $n\le 2^k$ initially, then after $2k$ steps we arrive at a situation with $n\le 2^0=1$. Since it takes one additional step to reach $n=0$ and terminate, and since initially we may have $n>m$, it seems we may need up to $2k+2$ rounds.

Indeed, the desired bounds are not fully correct, as for example $m=1$, $n=42$ (so $k=0$) requires $2$ instead of just $2\cdot 0=0$ steps: $(1,42)\mapsto (42,1)\mapsto ({\bf 1},0)$.

Remark: A deeper analysis should exhibit that the behaviour is governed by powers of the golden ration $\phi\approx 1.618$ rather than $\sqrt 2\approx 1.414$.

Solution 2:

This is just an informal sketch but might be useful. In each step you're dividing either by m (i.e. what's left from it) or by n (i.e. what's left from it). Both of them are >= 2 (as you're still dividing to them). So each time you're dividing at least by 2. The algorithm stops when you reach 1. So ... it's obvious that you can't divide more than k times i.e. do more than k steps (if you do more than k it would mean one of the numbers becomes 1 or smaller than 1, and you continue the algorithm, which is not possible).