Lamé’s Theorem

Lamé's Theorem is the result of Gabriel Lamé's analysis of the complexity of 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 Euclid's algorithm with entries $u\,\!$ and $v\,\!$ is less than $5$ times the number of decimal digits of $\min(u,v)\,\!$.

Demonstration

Given $u>v$ as integer and positive entries in Euclid's algorithm. Then:

$u=vq_{1}+v_{1},0<v_{1}<v$

$v=v_{1}q_{2}+v_{2},0<v_{2}<v_{1}$

$v_{1}=v_{2}q_{3}+v_{3},0<v_{3}<v_{2}$

$...$

$v_{n-2}=v_{n-1}q_{n}+v_{n},0<v_{n}<v_{n-1}$

$v_{n-1}=v_{n}q_{n+1}$

And considering the Fibonacci sequence $(1,1,2,3,5,8,13,...)$ given by the recurrence law

$F_{n}=\left\{{\begin{matrix}1,&{\mbox{if }}n=0\\1,&{\mbox{if }}n=1\\F_{n-1}+F_{n-2},&{\mbox{other cases}}\end{matrix}}\right.$

we have $v_{n}\geq 1$ and $v_{n-1}>2$, i. e., $v_{n}\geq F_{1}=1$ and $v_{n-1}\geq F_{2}=2$. So, in general, $v_{n-p}\geq F_{p+1}$ for $p=0,1,2,3,...,n-1$ so that by taking $v=v_{0}$, $v=v_{1}q_{2}+v_{2}\geq F_{n+1}$.

Considering the golden ratio $\phi ={\frac {1+{\sqrt {5}}}{2}}$ we observe that

$\phi ^{2}=\phi +1<2+1\leq f_{2}+f_{1}=f_{3}$

$\phi ^{3}=\phi ^{2}+\phi <f_{3}+2\leq f_{3}+f_{2}=f_{4}$

$\phi ^{4}=\phi ^{3}+\phi <f_{4}+f_{3}=f_{5}$

$\vdots$

$\phi ^{j}<f_{j+1},\;\;j=2,3,4,...$

As $F_{n+1}\geq v$ implies $\phi ^{j}<F_{j+1}<v$, it follows

$\log _{10}{\phi ^{n}}<\log _{10}{v}$

from which

$n<{\frac {\log _{10}{v}}{\log _{10}{\phi }}}.$

Besides, utilizing a calculator or other approximation method, one concludes that

${\frac {1}{\log _{10}{\phi }}}<5$

and, so,

$n<{\frac {\log _{10}v}{\log _{10}{\phi }}}<5\times \log _{10}{v}$

Given $k$ the number of digits of $v$ and the of 10, we have

$v=d_{k-1}10^{k-1}+d_{k-2}10^{k-2}+...+d_{1}10+d_{0}$

from which $v<10^{k}$ implies $\log _{10}v<\log _{10}{10^{k}}=k$. Therefore, $n<5k\implies n+1<5k$.

The Lamé's Theorem is thus demonstrated.

See also

• Euclidean algorithm
• Gabriel Lamé

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.

This article "Lamé’s Theorem" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Lamé’s Theorem. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---