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.

REFERENCES:

Honsberger, R. "A Theorem of Gabriel Lamé." Ch. 7 in Mathematical Gems II. Washington, DC: Math. Assoc. Amer., pp. 54-57, 1976.

Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1998.