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 x^7 + y^7 = z^7 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 a y b, al menos uno de ellos diferente de 0, se define como el divisor común d (es decir, d divide a a y a b) tal que, si e es también un divisor común, entonces e divide a d. En otras palabras, d 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 a y b crece exponencialmente con el número de dígitos de a y b. 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 a entre b, es decir, encontramos q y r tales que

a = qb + r, \qquad 0 \le r < b,

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

\text{mcd}(a,b) = \text{mcd}(b, r).

Si ahora dividimos b entre r, obtenemos entonces un residuo r', estrictamente menor a r, y que satisface \text{mcd}(b,r) = \text{mcd}(r,r'). 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 \text{mcd}(a,b).

Por ejemplo, si dividimos 360 entre 315 obtenemos que 360 = 1\times 315 + 45, y si dividimos 315 entre 45 obtenemos 315 = 7\times 45 + 0, 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 a \ge b > 0 enteros, y consideramos la sucesión r_1, r_2, \ldots, r_n de residuos obtenidos por división sucesiva, donde r_n = \text{mcd}(a,b):

a = q_1b + r_1, b = q_2r_1 + r_2, r_1 = q_3r_2 + r_3,\ldots r_{n-1} = q_{n+1}r_n.

Entonces n \le \dfrac{\log b}{\log \varphi}, donde \varphi = \dfrac{\sqrt{5}+1}{2} es la razón dorada.

Demostración: Consideramos la sucesión de Fibonacci F_n, construida con F_0 = 0, F_1 =1, y F_n + F_{n+1} = F_{n+2}. Entonces F_2 = 1, F_3 = 2,, etc.

Ahora bien, como r_n \ge 1,, entonces r_n \ge F_2. Además, como r_{n-1} > r_n, entonces r_{n-1} \ge 2 = F_3. Observamos también que

r_{n-2} = q_nr_{n-1} + r_n \ge r_{n-1} + r_n \ge F_3 + F_2 = F_4.

En general, para todo k, tenemos que r_{n-k} \ge F_{k+2}. En particular, regresamos a b después de n pasos, así que b \ge F_{n+2}.

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

F_n = \dfrac{\varphi^n - 1/\varphi^n}{\sqrt 5},

donde \varphi = \dfrac{1 + \sqrt 5}{2}. Tenemos entonces que

b \ge F_{n+2} = \dfrac{\varphi^{n+2} - 1/\varphi^{n+2}}{\sqrt 5} \ge \dfrac{\varphi^{n+2} - 1/\varphi^2}{\sqrt 5},

y por lo tanto, tomando logaritmos, n \le \dfrac{\log (b\sqrt 5 + 1/\varphi^2)}{\log \varphi} - 2 \le \dfrac{\log b}{\log \varphi}, porque

\dfrac{\log \big(\sqrt 5 + 1/(b\varphi^2)\big)}{\log \varphi} \le\dfrac{\log(\sqrt 5 + 1/\varphi^2)}{\log\varphi} = \dfrac{\log(1+\varphi)}{\log\varphi}=2.

Observamos que, si tomamos logaritmos base 10, obtenemos que

n \le \dfrac{\log_{10} b}{\log_{10}\varphi} < 5 \log_{10} b,

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 a y b son números de Fibonacci consecutivos.

7 comentarios en “Gabriel Lamé

  1. Pingback: La razón por la que el último teorema de Fermat escapó de las garras de Lamé - Gaussianos | Gaussianos

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s