For , let and be integers with such that the Euclidean
algorithm applied to
and requires exactly division steps and such that is as small as possible satisfying these conditions. Then
and , where is a Fibonacci number
(Knuth 1998, p. 343).

Furthermore, the number of steps in the Euclidean algorithm never exceeds 5 times the number of digits in the smaller number. In
fact, the bound 5 can be further reduced to , where is the golden ratio.