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

Hi there

Given the exercise

Let .

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 .

I don't find a meaningful beginning. I can write as a representation of k in the dual System. Then

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 ?

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 . So, . This implies that . If has digits, then . So, since , it must be that , implying has at most digits.