Lamé's theorem (another Prime Pages' Glossary entries)
 Glossary: Prime Pages: Top 5000: 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 integer n, let a > b be the least integers such that Euclid's algorithm applied to a and b requires exactly n division steps. Then a = un+2 and b = un+1 (where un is the nth 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) log a This is approximately 1.9405. log10 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: EuclideanAlgorithmReferences: 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]] Chris K. Caldwell © 1999-2018 (all rights reserved)