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

Question

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!

Answer 1

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

Answer 2

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