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 euclideanas 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 ${\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.

Bibliografía

• Bach, Eric (1996). Teoría algorítmica de números . Jeffrey Outlaw Shallit. Cambridge, Massachusetts: MIT Press.ISBN 0-262-02405-5ISBN 0-262-02405-5 .OCLC 33164327OCLC 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.