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 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.
Statement The number of division steps in the Euclidean algorithm with entries u {\displaystyle u\,\!} and v {\displaystyle v\,\!} is less than 5 {\displaystyle 5} times the number of decimal digits of min ( u , v ) {\displaystyle \min(u,v)\,\!} .
Proof Let u > v {\displaystyle u>v} be two positive integers. Applying to them the Euclidean algorithm provides two sequences ( q 1 , … , q n ) {\displaystyle (q_{1},\ldots ,q_{n})} and ( v 2 , … , v n ) {\displaystyle (v_{2},\ldots ,v_{n})} of positive integers such that, setting v 0 = u , {\displaystyle v_{0}=u,} v 1 = v {\displaystyle v_{1}=v} and v n + 1 = 0 , {\displaystyle v_{n+1}=0,} one has
v i − 1 = q i v i + v i + 1 {\displaystyle v_{i-1}=q_{i}v_{i}+v_{i+1}}
for i = 1 , … , n , {\displaystyle i=1,\ldots ,n,} and
u > v > v 2 > ⋯ > v n > 0. {\displaystyle u>v>v_{2}>\cdots >v_{n}>0.}
The number n 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 , {\displaystyle F_{0}=0,} F 1 = 1 , {\displaystyle F_{1}=1,} and
F n + 1 = F n + F n − 1 {\displaystyle F_{n+1}=F_{n}+F_{n-1}}
for n > 0. {\displaystyle n>0.}
The above relations show that v n ≥ 1 = F 2 , {\displaystyle v_{n}\geq 1=F_{2},} and v n − 1 ≥ 2 = F 3 . {\displaystyle v_{n-1}\geq 2=F_{3}.} By induction,
v n − i − 1 = q n − i v n − i + v n − i + 1 ≥ v n − i + v n − i + 1 ≥ F i + 2 + F i + 1 = F i + 3 . {\displaystyle {\begin{aligned}v_{n-i-1}&=q_{n-i}v_{n-i}+v_{n-i+1}\\&\geq v_{n-i}+v_{n-i+1}\\&\geq F_{i+2}+F_{i+1}=F_{i+3}.\end{aligned}}}
So, if the Euclidean algorithm requires n steps, one has v ≥ F n + 1 . {\displaystyle v\geq F_{n+1}.}
One has F k ≥ φ k − 2 {\displaystyle F_{k}\geq \varphi ^{k-2}} for every integer k > 2 {\displaystyle k>2} , where φ = 1 + 5 2 {\textstyle \varphi ={\frac {1+{\sqrt {5}}}{2}}} is the Golden ratio. This can be proved by induction, starting with F 2 = φ 0 = 1 , {\displaystyle F_{2}=\varphi ^{0}=1,} F 3 = 2 > φ , {\displaystyle F_{3}=2>\varphi ,} and continuing by using that φ 2 = φ + 1 : {\displaystyle \varphi ^{2}=\varphi +1:}
F k + 1 = F k + F k − 1 ≥ φ k − 2 + φ k − 3 = φ k − 3 ( 1 + φ ) = φ k − 1 . {\displaystyle {\begin{aligned}F_{k+1}&=F_{k}+F_{k-1}\\&\geq \varphi ^{k-2}+\varphi ^{k-3}\\&=\varphi ^{k-3}(1+\varphi )\\&=\varphi ^{k-1}.\end{aligned}}}
So, if n is the number of steps of the Euclidean algorithm, one has
v ≥ φ n − 1 , {\displaystyle v\geq \varphi ^{n-1},}
and thus
n − 1 ≤ log 10 v log 10 φ < 5 log 10 v , {\displaystyle n-1\leq {\frac {\log _{10}v}{\log _{10}\varphi }}<5\log _{10}v,}
using 1 log 10 φ < 5. {\textstyle {\frac {1}{\log _{10}\varphi }}<5.}
If k is the number of decimal digits of v {\displaystyle v} , one has v < 10 k {\displaystyle v<10^{k}} and log 10 v < k . {\displaystyle \log _{10}v<k.}
So,
n − 1 < 5 k , {\displaystyle n-1<5k,}
and, as both members of the inequality are integers,
n ≤ 5 k , {\displaystyle n\leq 5k,}
which is exactly what Lamé's theorem asserts. As a side result of this proof, one gets that the pairs of integers ( u , v ) {\displaystyle (u,v)} that give the maximum number of steps of the Euclidean algorithm (for a given size of v {\displaystyle v} ) are the pairs of consecutive Fibonacci numbers.
References
Bibliography Bach, Eric (1996). Algorithmic number theory. Jeffrey Outlaw Shallit. Cambridge, Mass.: MIT Press. ISBN 0-262-02405-5. OCLC 33164327 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.