Lamé's theorem states that 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. 360).
Furthermore, the number of steps in the Euclidean algorithm never exceeds 5 times the number of digits in the smaller number. More
precisely, if 
is a positive integer and 
, the number of division steps is at most 
, where
is the golden
ratio and 
denotes the floor function (Knuth 1998, p. 360).
