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=v{q}_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=\{\begin{array}{cc}1,& \text{se }n=0\\ 1,& \text{se }n=1\\ F_{n-1}+F_{n-2},& \text{outros casos}\end{array}$,

temos que $v_n\ge 1$ e $v_{n-1}>2$, isto é, $v_n\ge F_1=1$ e $v_{n-1}\ge F_2=2$. Então, de maneira geral, $v_{n-p}\ge 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\ge F_{n+1}$.

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

${\varphi }^2=\varphi +1<2+1\le f_2+f_1=f_3$

${\varphi }^3={\varphi }^2+\varphi <f_3+2\le f_3+f_2=f_4$

${\varphi }^4={\varphi }^3+\varphi <f_4+f_3=f_5$

$⋮$

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

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

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

de onde

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

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

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

e, portanto,

$n<\frac{{\log }_{10}v}{{\log }_{10}\varphi }<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⟹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.