TOPICS
Search

Lamé's Theorem


For n>=1, let u and v be integers with u>v>0 such that the Euclidean algorithm applied to u and v requires exactly n division steps and such that u is as small as possible satisfying these conditions. Then u=F_(n+2) and v=F_(n+1), where F_k 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 ln10/lnphi approx 4.785, where phi is the golden ratio.


See also

Euclidean Algorithm

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Lamé's Theorem

Cite this as:

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

Subject classifications