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

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

Hi there

Given the exercise

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

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 $log_2(k)$.

I don't find a meaningful beginning. I can write $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

$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

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

Edit:

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

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

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

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