Euclidean Algorithm : Confusion with how many divisions needed? The question asks how many the divisions required to find $\gcd(34,55)$.
I did it using the Euclidean Algorithm with the following result.
$$55=1 \cdot 34+21$$
$$34=1 \cdot 21+13$$
$$21=1 \cdot 13+8$$
$$13=1 \cdot 8+5$$
$$8=1 \cdot 5+3$$
$$5=1 \cdot 3+2$$
$$3=1 \cdot 2+1$$
$$2=2 \cdot 1+0$$
$$\gcd(34,55)=1$$
I wrote the answer $8$ since there are only $8$ steps needed, but the answer shown is $9$ divisions is required. I wonder if is the answer wrong or am I wrong?
 A: There is an uncertainty with finite continued fractions (which are a representation of the Euclidean algorithm). You can write:
$$\frac{34}{55}=\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{2}}}}}}}}$$
Here we have $8$ 'levels' of the continued fraction.
On the other hand, we can write:
$$\frac{34}{55}=\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1+\cfrac{1}{1}}}}}}}}}$$
And now we have $9$ 'levels'.
We used the fact that $2=1+1=1+\frac{1}{1}$.
To be clear, for any rational number we have two equivalent continued fraction represenations.
By the way, this fraction is very close to the (reciprocal) Golden Ratio.
A: The invariant in the Euclidean algorithm is that the gcd of consecutive numbers is constant.  Thus your computations prove that 
$$ (55,34) = (34,21) = (21,13) = (13,8) = (8,5) = (5,3) = (3,2) = (2,1) = (1,0)\ [ = 1]$$
using the normal convention the algorithm terminates when an argument is zero. Counting the number of gcds in the chain we get $\,9,\,$ not $\,8.\,$
A: Your method is not bad but I think using lame's theorem is the best idea here. Lame theorem give an estimate of number of steps needed to find the greatest common divisor of two integers using Euclidian algorithm.
