Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'd love your help with proving that if $a,b \in \mathbb{Z}$, $a>b>0$, $b<2^n$, then in the Euclidean algorithm for $\gcd(a,b)$ the number of steps(divisions) is not more than $2n$.

I tried to use the fact that the remainders $r_1,r_2,..$ in this algorithm satisfy $r_{i+2}<\frac{r_i}{2}$, but it doesn't really help.

Any suggestions?

Thanks a lot!

share|improve this question
    
Did you mean $r_{i+2}$? –  Thomas Andrews Mar 17 '12 at 15:27
    
Yes, Thanks. I fixed it. –  Jozef Mar 17 '12 at 15:32

2 Answers 2

up vote 2 down vote accepted

These are the crucial steps (for a modified division algorithm where $q$ is the nearest integer to the $b/a$): $$ \forall i:~ r_{i+1} \le \frac{r_i}{2} \quad \implies \quad \forall i:~ r_{i} \le 2^{-i}r_0 \quad \implies \quad r_{n} \le 2^{-n}b<1 $$ I'm assuming $r_0=\min(a,b)\le b <2^n$, and that each $r_i$ is the signed residue with smallest magnitude.

For Fibbonacci numbers $b=F_k=\frac{(1+\sqrt5)^k-(1-\sqrt5)^k}{2^k\sqrt5}$ and $a=F_{k-1}$ (representing a worst case analysis), if we start with $b=q_0a+r_0$, then we find $q_i=1~(\forall i)$, $r_0=F_k-F_{k-1}=F_{k-2}$, and by induction, $r_i=F_{k-i}-F_{k-i-1}=F_{k-i-2}$. This shows that the algorithm terminates when $i=k-2$. However, for $k$ large, $\log_2F_k\approx0.694241k-0.16096$ (using the dominating term). This furnishes an example where $b<2^n$ (for $n=\lceil0.694241k-0.16096\rceil$) requires $k-2>n$ steps, still much better than the $2n$ apparently required by the regular division algorithm.

For the regular division algorithm, where each integral quotient $q$ is the greatest integer less than or equal to the rational quotient -- also called the (mathematical) floor function (which is asymmetric, unlike its analogue in most computer language implementations, which is an odd function), and each remainder $r$ is non-negative, say we start and end as follows: $$ \eqalign{ a &=q_0\, b +r_0 &\qquad 0< r_0<b<2^n\\ b &=q_1\,r_0+r_1 &\qquad 0< r_1<r_0\\ r_0&=q_2\,r_1+r_2 &\qquad 0< r_2<r_1\\ &~\vdots \\ r_{m-2}&=q_m\,r_{m-1}+r_m &\qquad 0< r_m<r_{m-1}\\ r_{m-1}&=q_{m+1}\,r_m } $$ Now the worst case (slowest) "decay" of $\{r_k\}_{k=0}^m$ is also the best case (fastest) "growth" of $\{r_m,r_{m-1},\dots,r_0\}$. But we also know that it cannot be the case that $r_k=r_{k-1}-1$ for all $m\ge k\ge 0$ (and $m>1$). This is because as soon as $r_k$ gets so close to $r_{k-1}$ as $r_{k-1}-1$ we are at the "antepenultimate" step, i.e., the next remainder, $r_{k+1}$, will be one, the GCD. A graceful argument will in fact show that, in the worst case, the remainders $r_k$ decay by a factor of the golden ratio, $\phi=\frac{1+\sqrt5}{2}$, here as well, i.e. $r_k < \phi^{-k}r_0$. Since $\phi^2=\frac{3+\sqrt5}{2}>2$, we get the fact you mention in your OP, and an analogous argument to mine above gives us the bound with $2n$.

share|improve this answer
    
It's $i+2$, not $i+1$, but this is basically the answer. –  Thomas Andrews Mar 17 '12 at 15:34

If you know that $r_{i+2} < \frac{r_i}{2}$ than this is easy.

You can prove by induction that $r_{i+2k}< \frac{r_i}{2^k}$. Also, exactly the same way you prove that $r_{i+2} < \frac{r_i}{2}$ you can prove that $r_{2} < \frac{b}{2}$.

Then,

$$r_{2n} < \frac{r_2}{2^{n-1}}< \frac{b}{2^n} <1 \,.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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