Teorema de Lamé

Teorema de Lamé é o resultado da análise da complexidade do algoritmo de Euclides, feita por Gabriel Lamé. Usando os números de Fibonacci, ele provou que quando se busca o máximo divisor comum de dois inteiros a e b, o algoritmo termina em no máximo 5k passos, onde k é o número de dígitos (decimais) de b.

Enunciado

O número de passos de divisão no algoritmo de Euclides com entradas $u\,\!$ e $v\,\!$ é limitado superiormente por $5\,\!$ vezes a quantidade de dígitos decimais em $min(u,v)\,\!$ .

Demonstração

Sejam $u>v$ entradas inteiras e positivas no algoritmo de Euclides. Então:

$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}$

E considerando a sequência de Fibonacci $(1,1,2,3,5,8,13,...)$ dada pela lei de recorrência

$F_{n}=\left\{{\begin{matrix}1,&{\mbox{se }}n=0\\1,&{\mbox{se }}n=1\\F_{n-1}+F_{n-2},&{\mbox{outros casos}}\end{matrix}}\right.$ ,

temos que $v_{n}\geq 1$ e $v_{n-1}>2$ , isto é, $v_{n}\geq F_{1}=1$ e $v_{n-1}\geq F_{2}=2$ . Então, de maneira geral, $v_{n-p}\geq F_{p+1}$ para $p=0,1,2,3,...,n-1$ de modo que tomando $v=v_{0}$ , $v=v_{1}q_{2}+v_{2}\geq F_{n+1}$ .

Considerando a proporção áurea $\phi ={\frac {1+{\sqrt {5}}}{2}}$ observamos que

$\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,...$

Como $F_{n+1}\geq v$ implica $\phi ^{j}<F_{j+1}<v$ , segue que

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

de onde

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

Além disso, utilizando uma calculadora ou outro método de aproximação, conclui-se que

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

e, portanto,

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

Seja $k$ o número de dígitos de $v$ e a decomposição em potências de 10, temos que

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

de onde $v<10^{k}$ implica $\log _{10}v<\log _{10}{10^{k}}=k$ . Portanto, $n<5k\implies n+1<5k$ . Fica assim demonstrado o Teorema de Lamé.

Bibliografia

Eric Bach. Algorithmic Number Theory: Eficcient algorithms. Vol. 1. 1996. MIT Press 496 p. 1 ISBN 0262024055

João Bosco Pitombeira de Carvalho. Olhando mais de cima: Euclides, Fibonacci e Lamé. Revista do Professor de Matemática, São Paulo, n. 24, p.32-40, 2 sem. 1993.