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.
