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

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

• why does $n'' > 2^{k-1}$ imply that $max(m', n') > 2^k$ ? – ultrainstinct Oct 21 '15 at 1:56

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

• This is a reasonable approach, but it doesn't quite work. You imply that it will take no more than $k$ steps for numbers up to $2^k$, but the Fibonacci numbers are worse than this. $\gcd(987,1597)$ takes $14$ steps, while $2^{13}=8128,$ so we should be done more quickly. But we are allowed $2k$ steps. – Ross Millikan Oct 16 '15 at 14:22
• @RossMillikan You're right. That's interesting. It depends which algorithm exactly the OP is referring to. I even get 15 or 16 steps for your example (depending on the implementation). I just tried it with a computer program. – peter.petrov Oct 16 '15 at 14:42