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

#### Solutions Collecting From Web of "Proving the number of iterations in the Euclidean algorithm"

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

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