Lamé's theorem

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 ${\displaystyle u\,\!}$ and ${\displaystyle v\,\!}$ is less than ${\displaystyle 5}$ times the number of decimal digits of ${\displaystyle \min(u,v)\,\!}$.

Proof

Let ${\displaystyle u>v}$ be two positive integers. Applying to them the Euclidean algorithm provides two sequences ${\displaystyle (q_{1},\ldots ,q_{n})}$ and ${\displaystyle (v_{2},\ldots ,v_{n})}$ of positive integers such that, setting ${\displaystyle v_{0}=u,}$ ${\displaystyle v_{1}=v}$ and ${\displaystyle v_{n+1}=0,}$ one has

${\displaystyle v_{i-1}=q_{i}v_{i}+v_{i+1}}$

for ${\displaystyle i=1,\ldots ,n,}$ and

${\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 ${\displaystyle F_{0}=0,}$ ${\displaystyle F_{1}=1,}$ and

${\displaystyle F_{n+1}=F_{n}+F_{n-1}}$

for ${\displaystyle n>0.}$

The above relations show that ${\displaystyle v_{n}\geq 1=F_{2},}$ and ${\displaystyle v_{n-1}\geq 2=F_{3}.}$ By induction,

${\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 ${\displaystyle v\geq F_{n+1}.}$

One has ${\displaystyle F_{k}\geq \varphi ^{k-2}}$ for every integer ${\displaystyle k>2}$, where ${\textstyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}$ is the Golden ratio. This can be proved by induction, starting with ${\displaystyle F_{2}=\varphi ^{0}=1,}$ ${\displaystyle F_{3}=2>\varphi ,}$ and continuing by using that ${\displaystyle \varphi ^{2}=\varphi +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

${\displaystyle v\geq \varphi ^{n-1},}$

and thus

${\displaystyle n-1\leq {\frac {\log _{10}v}{\log _{10}\varphi }}<5\log _{10}v,}$

using ${\textstyle {\frac {1}{\log _{10}\varphi }}<5.}$

If k is the number of decimal digits of ${\displaystyle v}$, one has ${\displaystyle v<10^{k}}$ and ${\displaystyle \log _{10}v<k.}$ So,

${\displaystyle n-1<5k,}$

and, as both members of the inequality are integers,

${\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 ${\displaystyle (u,v)}$ that give the maximum number of steps of the Euclidean algorithm (for a given size of ${\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.