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.