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.

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.

CITE THIS AS:

Weisstein, Eric W. "Lamé's Theorem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/LamesTheorem.html