# Lamé's theorem

In 1845 G. Lame' proved the following theorem about the number of steps required by the Euclidean algorithm to find the gcd(*a*,*b*):

For a given positive integern, leta>bbe the least integers such that Euclid's algorithm applied toaandbrequires exactlyndivision steps. Thena=u_{n+2}andb=u_{n+1}(whereu_{n}is thenth Fibonacci number).

From this we see that the Euclidean algorithm for numbers at most *N* will take at most
ceiling(4.8 log(*N*)/log(10) - 0.32) steps.

Heilborn and Porter proved that the average number of steps the number of steps in
the Euclidean algorithm for numbers *a* ≤ *b*
is

((12 log 2)/π^{2}) loga

This is approximately 1.9405^{.} log_{10} *a*) steps
(see [Knuth81 section 4.5.3]).

A simpler way to say these results is that the number of steps in Euclid's algorithm for gcd(*a*,*b*) is

- at most five times the number of digits in the larger of
*a*or*b*, and - on the average is less than twice that number of digits.

**See Also:** EuclideanAlgorithm

**References:**

- Knuth81
D. E. Knuth,Seminumerical algorithms, 2nd edition, The Art of Computer Programming Vol, 2, Addison-Wesley, 1981. Reading MA,MR 83i:68003[This book is an excellent reference for anyone interested in the basic aspects of programming the algorithms mentioned in these pages. New edition: [Knuth97]]

Printed from the PrimePages <t5k.org> © Reginald McLean.