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 sobre “Gabriel Lamé”

holomorfo dice:

3 febrero, 2010 a las 3:13 am

Bien! En la conclusion del teorema falta el «menor o igual que»

Responder
ricardos dice:

3 febrero, 2010 a las 11:54 am

Gracias, ya está corregido.

Responder
Pingback: La razón por la que el último teorema de Fermat escapó de las garras de Lamé - Gaussianos | Gaussianos
Oscar Eduardo Gómez dice:

19 agosto, 2014 a las 10:41 pm

La segunda desigualdad después de «Tenemos entonces que» está mal ya que al suprimir la resta el número aumenta no disminuye

Responder
1. ricardos dice:
  
  19 agosto, 2014 a las 11:10 pm
  
  Gracias. Está corregido.
Oscar Eduardo Gómez dice:

25 septiembre, 2014 a las 12:18 pm

Como phi^2 = 1 + phi entonces log(1 + phi) / log(phi) = log(phi^2) / log(phi) = 2 en el texto aparece log(1 + phi) / log(phi) < 2

Responder
1. ricardos dice:
  
  26 septiembre, 2014 a las 12:34 am
  
  Gracias.