Euclidean algorithm: the number gets smaller with complexity log(k)

Hi there

Given the exercise

Let $\displaystyle 1 \le d \in \mathbb{N} , k=f*d+h , h<f$.

Firstly show that the variable h has (with respect to basis 2) less digits than k. Then conclude that the euclidean algorithm is (ends) in polynomial time in $\displaystyle log_2(k)$.

I don't find a meaningful beginning. I can write $\displaystyle k=k_{d_k} k_{d_k-1} ... k_1 k_0 \text{ while } k_i \in \{0,1\} \forall i$ as a representation of k in the dual System. Then

$\displaystyle k=k_{d_k} k_{d_k-1} ... k_1 k_0 = \underbrace{f_{d_f} ... f_0}_{=f} * \underbrace{d_{d_d} ... d_0}_{=d} + \underbrace{h_{d_h} ... h_0}_{=h} $

Ok that far. Now what is here the idea? I don't see a track honestly ...

Regards

Re: Euclidean algorithm: the number gets smaller with complexity log(k)

Edit:

Do you also have $\displaystyle 0\le h < f$?

Re: Euclidean algorithm: the number gets smaller with complexity log(k)

Well it's not written on the exercise sheet but I think we can assume that all those numbers are non-negative integers...

Re: Euclidean algorithm: the number gets smaller with complexity log(k)

You have $\displaystyle h < f = \dfrac{k-h}{d}$. So, $\displaystyle h(d+1) < k$. This implies that $\displaystyle h < \dfrac{k}{d+1} \le \dfrac{k}{1+1} = \dfrac{k}{2}$. If $\displaystyle k$ has $\displaystyle n$ digits, then $\displaystyle k < 2^n$. So, since $\displaystyle h < \dfrac{k}{2}$, it must be that $\displaystyle h < \dfrac{k}{2} < 2^{n-1}$, implying $\displaystyle h$ has at most $\displaystyle n-1$ digits.