Gabriel Lamé

Gabriel Lamé, 1795-1870, fue un matemático francés que trabajó en diversas áreas, principalmente en la matemáticas aplicadas a la ingeniería. Después de estudiar su licenciatura en la École Polytechnique, Lamé estudió ingeniería en la École des Mines, de donde se graduó en 1820.

Al terminar sus estudios Lamé se mudó a Rusia, a donde diversos científicos franceses habían emigrado tanto por el desorden y la represión de la monarquía restaurada en Francia, como por el interés del zar Alejandro I en desarrollar la ciencia en su país. En San Petersburgo, Lamé se dedicó no solo al desarrollo urbano de la ciudad, sino también a la divulgación de las ideas de Cauchy en el análisis matemático.

Lamé regresó a Francia en 1832, donde inició su propia compañía de ingeniería, y más adelante ocupó la cátedra de física en la École Polytechnique. Nunca dejó su trabajo como ingeniero, y participó en diversos proyectos de desarrollo como la construcción de los ferrocarriles de París a Versalles y de París a Saint Germain.

Las aportaciones matemáticas de Lamé incluyen resultados en la teoría de coordenadas curvilíneas, la geometría diferencial y la teoría de números. Lamé fue el primero en demostrar que la ecuación no tiene soluciones enteras no triviales, y también es recordado por su resultado en la complejidad del algoritmo de Euclides, del cual voy a hablar a continuación.

El máximo común divisor de dos números enteros y , al menos uno de ellos diferente de , se define como el divisor común (es decir, divide a y a ) tal que, si es también un divisor común, entonces divide a . En otras palabras, es el divisor más grande. Sin un algoritmo sofisticado, para encontrar el máximo común divisor de dos enteros, digamos 360 y 315, tendríamos que comparar la lista de divisores de cada uno (1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360 son los divisores de 360, mientras que los divisores de 315 son 1, 3, 5, 7, 9, 15, 21, 35, 45, 63, 105, 315), comparar los divisores comunes (de 360 y 315 son 1, 3, 5, 9, 15 y 45) y tomar el mayor. Así, por ejemplo, obtenemos que el máximo común divisor de 360 y 315 es 45, y escribimos mcd(360, 315) = 45.

Sin embargo, vemos que el trabajo (número de operaciones) que toma el calcular todos los divisores de los números y crece exponencialmente con el número de dígitos de y . De hecho, encontrar un solo divisor no trivial de un número (factorizar) es una tarea muy compleja, y es prácticamente imposible si el número tiene, digamos, unos 200 dígitos.

Afortunadamente contamos con un algoritmo, conocido como el algoritmo de Euclides, para obtener el máximo común divisor de dos números sin necesidad de calcular todos sus divisores. Este parte de la observación que, si dividimos entre , es decir, encontramos y tales que

entonces cada divisor común de y es también divisor de , y cualquier divisor común de y es también divisor de , así que tenemos

Si ahora dividimos entre , obtenemos entonces un residuo , estrictamente menor a , y que satisface . De continuar dividiendo, en algún momento llegaremos a residuo igual a 0, y por lo tanto el último residuo distinto de 0 será igual a .

Por ejemplo, si dividimos 360 entre 315 obtenemos que , y si dividimos 315 entre 45 obtenemos , por lo que entonces obtenemos mcd(360,315) = 45, ¡en una sola operación!

No es sorpresa que el algoritmo de Euclides requiera de pocas operaciones para obtener el máximo común divisor de dos números. De hecho, Lamé demostró el siguiente teorema.

Teorema (Lamé). Sean enteros, y consideramos la sucesión de residuos obtenidos por división sucesiva, donde :

Entonces , donde es la razón dorada.

Demostración: Consideramos la sucesión de Fibonacci , construida con , y . Entonces , etc.

Ahora bien, como , entonces . Además, como entonces Observamos también que

En general, para todo , tenemos que En particular, regresamos a después de pasos, así que

La expresión explícita para cada está dada por

donde Tenemos entonces que

y por lo tanto, tomando logaritmos, , porque

Observamos que, si tomamos logaritmos base 10, obtenemos que

y entonces el número de divisiones en el algoritmo de Euclides para encontrar el máximo común divisor de dos números es menor a 5 veces el número de dígitos del más pequeño. También observamos que la peor situación posible, como se ve en la demostración del teorema de Lamé, ocurre cuando y son números de Fibonacci consecutivos.

Anuncios