Lamé's theorem

Short description: Theorem related to the Euclidean algorithm.

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 Euclidean algorithm with entries [math]\displaystyle{ u\,\! }[/math] and [math]\displaystyle{ v\,\! }[/math] is less than [math]\displaystyle{ 5 }[/math] times the number of decimal digits of [math]\displaystyle{ \min(u,v)\,\! }[/math].

Proof

Let [math]\displaystyle{ u\gt v }[/math] be two positive integers. Applying to them the Euclidean algorithm provides two sequences [math]\displaystyle{ (q_1,\ldots, q_{n}) }[/math] and [math]\displaystyle{ (v_2,\ldots, v_{n}) }[/math] of positive integers such that, setting [math]\displaystyle{ v_0=u, }[/math] [math]\displaystyle{ v_1=v }[/math] and [math]\displaystyle{ v_{n+1}=0, }[/math] one has

[math]\displaystyle{ v_{i-1}=q_iv_i +v_{i+1} }[/math]

for [math]\displaystyle{ i=1,\ldots, n, }[/math] and

[math]\displaystyle{ u\gt v\gt v_2\gt \cdots \gt v_{n}\gt 0. }[/math]

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 [math]\displaystyle{ F_0=0, }[/math] [math]\displaystyle{ F_1=1, }[/math] and

[math]\displaystyle{ F_{n+1}=F_n+F_{n-1} }[/math]

for [math]\displaystyle{ n\gt 0. }[/math]

The above relations show that [math]\displaystyle{ v_{n}\ge 1=F_2, }[/math] and [math]\displaystyle{ v_{n-1}\ge 2=F_3. }[/math] By induction,

[math]\displaystyle{ \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} }[/math]

So, if the Euclidean algorithm requires n steps, one has [math]\displaystyle{ v\ge F_{n+1}. }[/math]

One has [math]\displaystyle{ F_{k}\ge \varphi^{k-2} }[/math] for every integer [math]\displaystyle{ k\gt 2 }[/math], where [math]\displaystyle{ \varphi=\frac {1+\sqrt 5}2 }[/math] is the Golden ratio. This can be proved by induction, starting with [math]\displaystyle{ F_2 =\varphi^0=1, }[/math] [math]\displaystyle{ F_3=2\gt \varphi, }[/math] and continuing by using that [math]\displaystyle{ \varphi^2=\varphi +1: }[/math]

[math]\displaystyle{ \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} }[/math]

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

[math]\displaystyle{ v\ge \varphi^{n-1}, }[/math]

and thus

[math]\displaystyle{ n-1 \le \frac {\log_{10} v}{\log_{10} \varphi}\lt 5\log_{10} v, }[/math]

using [math]\displaystyle{ \frac 1{\log_{10} \varphi}\lt 5. }[/math]

If k is the number of decimal digits of [math]\displaystyle{ v }[/math], one has [math]\displaystyle{ v\lt 10^k }[/math] and [math]\displaystyle{ \log_{10} v\lt k. }[/math] So,

[math]\displaystyle{ n-1\lt 5k, }[/math]

and, as both members of the inequality are integers,

[math]\displaystyle{ n\le 5k, }[/math]

which is exactly what Lamé's theorem asserts.

As a side result of this proof, one gets that the pairs of integers [math]\displaystyle{ (u,v) }[/math] that give the maximum number of steps of the Euclidean algorithm (for a given size of [math]\displaystyle{ v }[/math]) are the pairs of consecutive Fibonacci numbers.

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.