Lamé's Theorem
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.
Contact the MathWorld Team
greatest common divisor