2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Oct 16 '15 at 14:22
  • $\begingroup$ @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. $\endgroup$ – peter.petrov Oct 16 '15 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.