Lamé's theorem explained

Lamé's Theorem is the result of Gabriel Lamé's analysis of the complexity of the Euclidean algorithm. Using Fibonacci numbers, he proved in 1844^{[1] [2]} that when looking for the greatest common divisor (GCD) of two integers a and b, the algorithm finishes in at most 5k steps, where k is the number of digits (decimal) of b.^{[3] [4]}

Statement

The number of division steps in Euclidean algorithm with entries

u and v is less than 5 times the number of decimal digits of min (u,v) .

Proof

Let

u>v be two positive integers. Applying to them the Euclidean algorithm provides two sequences (q _{1,\ldots,} q _{n} ) and (v _{2,\ldots,} v _{n} ) of positive integers such that, setting v _{0=u,} v _{1=v} and v _{n+1} =0 , one hasv _{i-1} = q _{iv} _{i} + v _{i+1} for i =1 ,\ldots, n, andu>v>v _{2> …} >v _{n} > 0 . The number is called the number of steps of the Euclidean algorithm, since it is the number of Euclidean divisions that are performed.

The Fibonacci numbers are defined by

F _{0=0,} F _{1=1,} and F _{n+1} = F _{n+F} _{n-1} for n> 0 .

The above relations show that

v _{n} \ge 1= F _{2,} and v _{n-1} \ge 2= F _{3.} By induction,\begin{align} v _{n-i-1} & = q _{n-i} v _{n-i} + v _{n-i+1} \\ &\ge v _{n-i} + v _{n-i+1} \\ &\ge F _{i+2} + F _{i+1} = F _{i+3} . \end{align} So, if the Euclidean algorithm requires steps, one has v\ge F _{n+1} .

One has

F _{k} \ge \varphi ^{k-2} for every integer k> 2 , where $\backslash varphi=\backslash frac\; 2$ is the Golden ratio. This can be proved by induction, starting with F _{2} = \varphi ^{0=1,} F _{3=2>} \varphi, and continuing by using that \varphi ^{2=\varphi} +1 : \begin{align} F _{k+1} & = F _{k+F} _{k-1} \\ &\ge \varphi ^{k-2} + \varphi ^{k-3} \\ & = \varphi ^{k-3} ( 1+ \varphi)\\ & = \varphi ^{k-1} . \end{align}

So, if is the number of steps of the Euclidean algorithm, one has

v\ge \varphi ^{n-1} , and thusn -1 \le (log _{10} v)/(log _{10} \varphi) < 5log _{10} v, using

If is the number of decimal digits of

v , one has v< 10 ^{k} and log _{10} v<k. So,n -1 < 5 k, and, as both members of the inequality are integers,n\le 5 k, which is exactly what Lamé's theorem asserts.

As a side result of this proof, one gets that the pairs of integers

(u,v) that give the maximum number of steps of the Euclidean algorithm (for a given size of v ) are the pairs of consecutive Fibonacci numbers.

Bibliography

• Bach, Eric (1996). Algorithmic number theory. Jeffrey Outlaw Shallit. Cambridge, Mass.: MIT Press. .
• Carvalho, João Bosco Pitombeira de (1993). Olhando mais de cima: Euclides, Fibonacci e Lamé. Revista do Professor de Matemática, São Paulo, n. 24, p. 32-40, 2 sem.

Notes and References

1. Lamé . Gabriel . 1844 . Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers . Comptes rendus des séances de l'Académie des Sciences . French . 19 . 867–870.
2. Shallit . Jeffrey . 1994-11-01 . Origins of the analysis of the Euclidean algorithm . Historia Mathematica . en . 21 . 4 . 401–419 . 10.1006/hmat.1994.1031 . 0315-0860. free .
3. Web site: Weisstein . Eric W. . Lamé's Theorem . 2023-05-09 . mathworld.wolfram.com . en.
4. Web site: Lame's Theorem - First Application of Fibonacci Numbers . 2023-05-09 . www.cut-the-knot.org.