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.^[1]​^[2]​ Este teorema afirma que cuando se busca el máximo común divisor (MCD) de dos enteros ${\displaystyle a\,\!}$ y ${\displaystyle b\,\!}$, con ${\displaystyle a>b\,\!}$, el algoritmo de Euclides termina en a lo sumo ${\displaystyle 5k\,\!}$ pasos (divisiones); donde ${\displaystyle k\,\!}$ es el número de dígitos de ${\displaystyle b\,\!}$ (expresado en base decimal).^[3]​ La prueba del Teorema utiliza la sucesión de Fibonacci.^[4]​

Enunciado del Teorema

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

Ejemplo

Supongamos que se aplica el algoritmo de Euclides con entradas ${\displaystyle a=1235\,\!}$ y ${\displaystyle 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 ${\displaystyle 5}$ veces el número de dígitos decimales de ${\displaystyle \min(1235,455)=455\,\!}$. Es decir, la cantidad de pasos es menor o igual a ${\displaystyle 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:$${\displaystyle {\begin{array}{l}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 ${\displaystyle a>b}$ dos números enteros positivos. Supongamos que aplicamos el algoritmo de Euclides a estos dos enteros, y que el algoritmo termina en ${\displaystyle n}$ pasos (divisiones enteras). Es decir:$${\displaystyle {\begin{array}{l}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}\\\vdots \\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 ${\displaystyle (q_{1},\ldots ,q_{n})}$ y ${\displaystyle (r_{2},\ldots ,r_{n})}$. Si definimos ${\displaystyle r_{0}=a,}$ ${\displaystyle r_{1}=b}$ y ${\displaystyle r_{n 1}=0}$, se puede expresar cada paso del algoritmo de forma compacta mediante: ${\displaystyle r_{i-1}=q_{i}r_{i} r_{i 1},\ \forall \ i=1,\ldots ,n.}$

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

Como ya fue dicho, el número n 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 ${\displaystyle r_{n 1}=0}$ .

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

$${\displaystyle F_{0}=0,\ F_{1}=1,\ F_{n 1}=F_{n} F_{n-1},\ \forall \ n\geq 1.}$$

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

Dado que ${\displaystyle r_{n}}$ es un entero positivo, se cumple: ${\displaystyle r_{n}\geq 1=F_{2}}$. Por otro lado, dado que ${\displaystyle r_{n-1}=q_{n}r_{n}}$, para ver que ${\displaystyle r_{n-1}\geq 2=F_{3}}$, basta con probar que se cumple ${\displaystyle q_{n}\geq 2}$. Para ver esto último, supongamos por absurdo que fuese ${\displaystyle q_{n}=0}$ o ${\displaystyle q_{n}=1}$. En el primer caso se tendría: ${\displaystyle r_{n-1}=q_{n}r_{n}=0}$; lo cual contradice la hipótesis de que el primer resto nulo es ${\displaystyle r_{n 1}}$. Por otro lado, si fuese si fuese ${\displaystyle q_{n}=1}$, se tendría: ${\displaystyle r_{n-1}=q_{n}r_{n}=r_{n}}$, lo cual a su vez implicaría: ${\displaystyle 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 ${\displaystyle r_{n 1}}$. La hipótesis de inducción fuerte consiste en asumir que se cumple: ${\displaystyle r_{n-k}\geq F_{k 2},\ \forall \ k$ Usando esto, queremos probar que se cumple la propiedad para el índice ${\displaystyle i}$: ${\displaystyle r_{n-i}\geq F_{i 2}}$. Para ver esto, escribimos:

$${\displaystyle {\begin{aligned}r_{n-i}&=q_{n-i 1}r_{n-i 1} r_{n-i 2}\\&\geq r_{n-i 1} r_{n-i 2}=r_{n-(i-1)} r_{n-(i-2)}\\&\geq F_{i 1} F_{i}=F_{i 2}.\end{aligned}}}$$

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

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

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

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

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

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

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

Como resultado secundario de esta prueba, se obtiene que los pares de números enteros ${\displaystyle (a,b)}$ que dan el número máximo de pasos del algoritmo de Euclides (para un tamaño fijo de ${\displaystyle b}$), 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.ISBN 0-262-02405-5. OCLC 33164327
• 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.