Teorema de Lamé

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.

• 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.