If is the smallest Integer for which there is a smaller Integer such that and generate a Euclidean Algorithm remainder sequence with steps, then is the Fibonacci Number . Furthermore, the number of steps in the Euclidean Algorithm never exceeds 5 times the number of digits in the smaller number.
See also Euclidean Algorithm
References
Honsberger, R. ``A Theorem of Gabriel Lamé.'' Ch. 7 in Mathematical Gems II.
Washington, DC: Math. Assoc. Amer., pp. 54-57, 1976.