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<i.}$ 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)<d\log _{10}(10)=d}$. 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

1. Lamé, Gabriel (1844). «Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers». Comptes rendus des séances de l'Académie des Sciences (en francés) 19: 867-870.
2. Shallit, Jeffrey (1 de noviembre de 1994). «Origins of the analysis of the Euclidean algorithm». Historia Mathematica (en inglés) 21 (4): 401-419. ISSN 0315-0860. doi:10.1006/hmat.1994.1031.
3. Weisstein, Eric W. «Lamé's Theorem». mathworld.wolfram.com (en inglés). Consultado el 9 de mayo de 2023.
4. «Lame's Theorem - First Application of Fibonacci Numbers». www.cut-the-knot.org. Consultado el 9 de mayo de 2023.

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.