# 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}{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 $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}{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 $(q_{1},\ldots ,q_{n})$ y $(r_{2},\ldots ,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},\ \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: $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 $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},\ \forall \ n\geq 1.$
Vamos a probar la siguiente relación entre la sucesión de Fibonacci y los restos del algoritmo de Euclides: $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 $i$. El paso base consiste en probar que: $r_{n}\geq F_{2}=1$ y $r_{n-1}\geq F_{3}=2$.
Dado que $r_{n}$ es un entero positivo, se cumple: $r_{n}\geq 1=F_{2}$. Por otro lado, dado que $r_{n-1}=q_{n}r_{n}$, para ver que $r_{n-1}\geq 2=F_{3}$, basta con probar que se cumple $q_{n}\geq 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}\geq F_{k+2},\ \forall \ k<i.$ Usando esto, queremos probar que se cumple la propiedad para el índice $i$: $r_{n-i}\geq F_{i+2}$. Para ver esto, escribimos:
${\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: $q_{s}\geq 1,\ \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 n es la cantidad de pasos del algoritmo de Euclides.
En particular, probamos que se cumple: $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 $F_{k}\geq \varphi ^{k-2}$, para cada entero $k>2$; dónde φ=(1+√5)/2 {\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: $F_{2}=\varphi ^{0}=1$, $F_{3}=2>\varphi$. Usando que $\varphi ^{2}=\varphi +1$, el paso inductivo es: $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: $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:
$\log _{10}(b)\geq \log _{10}(F_{n+1})\geq (n-1)\log _{10}(\varphi )$. Como $\log _{10}(\varphi )>0$, podemos despejar y obtener: $n-1\leq {\frac {\log _{10}(b)}{\log _{10}(\varphi )}}$. Usando que ${\frac {1}{\log _{10}(\varphi )}}\simeq 4.785<5$, se obtiene: $n-1\leq {\frac {\log _{10}(b)}{\log _{10}(\varphi )}}<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\Leftrightarrow n<5d+1\leq 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.