Teorema de Lamé

El Teorema de Lamé es un resultado de Gabriel Lamé, publicado en 1844, que trata sobre la complejidad del Algoritmo de Euclides. Este teorema afirma que cuando se busca el máximo común divisor (MCD) de dos enteros $a$ y $b$, con $a>b$, el algoritmo de Euclides termina en a lo sumo $5k$ pasos (divisiones); donde $k$ es el número de dígitos de $b$ (expresado en base decimal). La prueba del Teorema utiliza la sucesión de Fibonacci.

Enunciado del Teorema

Supongamos que se aplica el algoritmo de Euclides con entradas enteras no negativas $a$ y $b$. El número de pasos (divisiones) que requiere el algoritmo para finalizar, es menor o igual que $5$ veces el número de dígitos decimales de $\min (a,b)$ (la entrada de menor magnitud).

Ejemplo

Supongamos que se aplica el algoritmo de Euclides con entradas $a=1235$ y $b=455$. El teorema de Lamé afirma que el número de pasos (divisiones) que requiere el algoritmo para finalizar, es menor o igual que $5$ veces el número de dígitos decimales de $\min (1235,455)=455$. Es decir, la cantidad de pasos es menor o igual a $5\times 3=15$.

Podemos comparar esta cota con la cantidad exacta de pasos que requiere el algoritmo de Euclides en este ejemplo. Los pasos del algoritmo son los siguientes:$$\begin{array}{c}1235=2\times 455+325,\\ 455=1\times 325+130,\\ 325=2\times 130+65,\\ 130=2\times 65+0.\end{array}$$El algoritmo termina en 4 pasos (divisiones), que es menor a la cota de 15 pasos del Teorema de Lamé.

Prueba del Teorema

Sean $a>b$ dos números enteros positivos. Supongamos que aplicamos el algoritmo de Euclides a estos dos enteros, y que el algoritmo termina en $n$ pasos (divisiones enteras). Es decir:$$\begin{array}{c}a=q_{1}b+r_2,\\ b=q_2{r}_2+r_3,\\ r_2=q_3{r}_3+r_4\\ r_3=q_4{r}_4+r_5\\ ⋮\\ r_{n-2}=q_{n-1}{r}_{n-1}+r_n\\ r_{n-1}=q_n{r}_n+0.\end{array}$$

De esta forma se obtienen dos sucesiones de números enteros positivos, que denotamos $(q_1,\dots ,q_n)$ y $(r_2,\dots ,r_n)$. Si definimos $r_0=a,$ $r_1=b$ y $r_{n+1}=0$, se puede expresar cada paso del algoritmo de forma compacta mediante: $r_{i-1}=q_i{r}_i+r_{i+1},\mathrm{\forall }i=1,\dots ,n.$

Además, sabemos que la sucesión de los restos es estrictamente decreciente (por definición de resto). Es decir: $$a>b>r_2>\cdots >r_n>r_{n+1}=0.$$

Como ya fue dicho, el número Plantilla:Mvar es el número de pasos del algoritmo de Euclides, ya que es el número de divisiones euclidianas que se realizan hasta obtener resto nulo $r_{n+1}=0$ .

Consideremos ahora la sucesión de Fibonacci. Esta sucesión se puede definir de forma recursiva mediante:

$$F_0=0,F_1=1,F_{n+1}=F_n+F_{n-1},\mathrm{\forall }n\ge 1.$$

Vamos a probar la siguiente relación entre la sucesión de Fibonacci y los restos del algoritmo de Euclides: $r_{n-i}\ge F_{i+2},\mathrm{\forall }i=0,1,\dots ,n.$ La prueba será mediante el método de inducción fuerte en $i$. El paso base consiste en probar que: $r_n\ge F_2=1$ y $r_{n-1}\ge F_3=2$.

Dado que $r_n$ es un entero positivo, se cumple: $r_n\ge 1=F_2$. Por otro lado, dado que $r_{n-1}=q_n{r}_n$, para ver que $r_{n-1}\ge 2=F_3$, basta con probar que se cumple $q_n\ge 2$. Para ver esto último, supongamos por absurdo que fuese $q_n=0$ o $q_n=1$. En el primer caso se tendría: $r_{n-1}=q_n{r}_n=0$; lo cual contradice la hipótesis de que el primer resto nulo es $r_{n+1}$. Por otro lado, si fuese si fuese $q_n=1$, se tendría: $r_{n-1}=q_n{r}_n=r_n$, lo cual a su vez implicaría: $r_{n-2}=q_{n-1}{r}_{n-1}+r_n=q_{n-1}{r}_{n-1}+r_{n-1}=r_{n-1}(q_{n-1}+1)$. Nuevamente, esto contradice la hipótesis de que el primer resto nulo es $r_{n+1}$. La hipótesis de inducción fuerte consiste en asumir que se cumple: $r_{n-k}\ge F_{k+2},\mathrm{\forall }k<i.$ Usando esto, queremos probar que se cumple la propiedad para el índice $i$: $r_{n-i}\ge F_{i+2}$. Para ver esto, escribimos:

$$\begin{array}{cc}{r}_{n-i}& =q_{n-i+1}{r}_{n-i+1}+r_{n-i+2}\\ & \ge r_{n-i+1}+r_{n-i+2}=r_{n-(i-1)}+r_{n-(i-2)}\\ & \ge F_{i+1}+F_i=F_{i+2}.\end{array}$$

Notar que en la penúltima desigualdad utilizamos que los cocientes son siempre enteros no nulos: $q_s\ge 1,\mathrm{\forall }s$. Si esto no fuese cierto, tendríamos un resto nulo anterior a $r_{n+1}$, lo cual contradice la hipótesis de que Plantilla:Mvar es la cantidad de pasos del algoritmo de Euclides.

En particular, probamos que se cumple: $b=r_1=r_{n-(n-1)}\ge F_{n+1}.$

Por otro lado, por propiedades de la sucesión de Fibonacci, sabemos que se cumple $F_k\ge {\phi }^{k-2}$, para cada entero $k>2$; dónde $\phi =\frac{1+\sqrt{5}}{2}$ es la proporción áurea.

[Esta propiedad se puede probar mediante inducción fuerte, comenzando con el paso base: $F_2={\phi }^0=1$, $F_3=2>\phi$. Usando que ${\phi }^2=\phi +1$, el paso inductivo es: $F_{k+1}=F_k+F_{k-1}\ge {\phi }^{k-2}+{\phi }^{k-3}={\phi }^{k-3}(1+\phi )={\phi }^{k-1}.$]

Por lo tanto, juntando las últimas dos desigualdades: $b\ge F_{n+1}\ge {\phi }^{n-1}.$ Como los números son positivos, al aplicar logaritmo se mantiene el sentido de las desigualdades. Es decir:

${\log }_{10}(b)\ge {\log }_{10}(F_{n+1})\ge (n-1){\log }_{10}(\phi )$. Como ${\log }_{10}(\phi )>0$, podemos despejar y obtener: $n-1\le \frac{{\log }_{10}(b)}{{\log }_{10}(\phi )}$. Usando que $\frac{1}{{\log }_{10}(\phi )}\simeq 4.785<5$, se obtiene: $n-1\le \frac{{\log }_{10}(b)}{{\log }_{10}(\phi )}<5{\log }_{10}(b)$.

Para terminar, notar que si $d$ es la cantidad de dígitos decimales de $b$, se cumple: $b<10^d$. Es decir: ${\log }_{10}(b)<d{\log }_{10}(10)=d$. Reemplazando esta cota, y despejando, se obtiene la cota buscada para la cantidad de pasos del algoritmo de Euclides: $n-1<5d\iff n<5d+1\le 5d$.

Como resultado secundario de esta prueba, se obtiene que los pares de números enteros $(a,b)$ que dan el número máximo de pasos del algoritmo de Euclides (para un tamaño fijo de $b$), son los pares de números de Fibonacci consecutivos.

Bibliografía

• Bach, Eric (1996). Teoría algorítmica de números . Jeffrey Outlaw Shallit. Cambridge, Massachusetts: MIT Press.Plantilla:ISBN. Plantilla:OCLC
• Carvalho, João Bosco Pitombeira de (1993). Olhando mais de cima : Euclides, Fibonacci y Lamé . Revista do Professor de Matemática, São Paulo, n. 24, pág. 32-40, 2 sem.