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 y , con , el algoritmo de Euclides termina en a lo sumo pasos (divisiones); donde es el número de dígitos de (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 y . El número de pasos (divisiones) que requiere el algoritmo para finalizar, es menor o igual que veces el número de dígitos decimales de (la entrada de menor magnitud).
Ejemplo Supongamos que se aplica el algoritmo de Euclides con entradas y . El teorema de Lamé afirma que el número de pasos (divisiones) que requiere el algoritmo para finalizar, es menor o igual que veces el número de dígitos decimales de . Es decir, la cantidad de pasos es menor o igual a .
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:El algoritmo termina en 4 pasos (divisiones), que es menor a la cota de 15 pasos del Teorema de Lamé.
Prueba del Teorema Sean dos números enteros positivos. Supongamos que aplicamos el algoritmo de Euclides a estos dos enteros, y que el algoritmo termina en pasos (divisiones enteras). Es decir:
De esta forma se obtienen dos sucesiones de números enteros positivos, que denotamos y . Si definimos y , se puede expresar cada paso del algoritmo de forma compacta mediante:
Además, sabemos que la sucesión de los restos es estrictamente decreciente (por definición de resto). Es decir:
Como se dijo, 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 .
Consideremos ahora la sucesión de Fibonacci. Esta sucesión se puede definir de forma recursiva mediante:
Vamos a probar la siguiente relación entre la sucesión de Fibonacci y los restos del algoritmo de Euclides: La prueba será mediante el método de inducción fuerte en .
El paso base consiste en probar que y .
Dado que es un entero positivo, se cumple: . Por otro lado, dado que , para ver que , basta con probar que se cumple . Para ver esto último, supongamos que fuese o . En el primer caso se tendría: ; lo cual contradice la hipótesis de que el primer resto nulo es . Por otro lado, si fuese , se tendría: , lo cual a su vez implicaría: . Nuevamente, esto contradice la hipótesis de que el primer resto nulo es .
La hipótesis de inducción fuerte consiste en suponer que se cumple
Usando esto, queremos probar que se cumple la propiedad para el índice : .
Para ver esto, escribimos:
Nótese que en la penúltima desigualdad los cocientes son siempre enteros no nulos: . Si esto no fuese cierto, tendríamos un resto nulo anterior a , lo cual contradice la hipótesis de que es la cantidad de pasos del algoritmo de Euclides.
En particular, probamos que se cumple:
Por otro lado, por propiedades de la sucesión de Fibonacci, sabemos que se cumple , para cada entero ; dónde es la proporción áurea.
[Esta propiedad se puede probar mediante inducción fuerte, comenzando con el paso base: , . Usando que , el paso inductivo es: ]
Por lo tanto, juntando las últimas dos desigualdades: Como los números son positivos, al aplicar logaritmo se mantiene el sentido de las desigualdades. Es decir:
. Como , podemos despejar y obtener: . Usando que , se obtiene: .
Para terminar, nótese que si es la cantidad de dígitos decimales de , se cumple: . Es decir: . Reemplazando esta cota y despejando, se obtiene la cota buscada para la cantidad de pasos del algoritmo de Euclides: .
Como resultado secundario de esta prueba, se obtiene que los pares de números enteros que dan el número máximo de pasos del algoritmo de Euclides (para un tamaño fijo de ), son los pares de números de Fibonacci consecutivos.
Referencias
Bibliografía
Bach, Eric (1996). Teoría algorítmica de números . Jeffrey Outlaw Shallit. Cambridge, Massachusetts: MIT Press.. 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.
Categoría:Euclides Categoría:Tecnologías de la información Categoría:Algoritmos Categoría:Teoremas de teoría de números Categoría:Complejidad computacional