Hace unos días veo este post en Futility Closet:

Mersenne once wrote to Fermat asking whether 100895598169 were a prime number.

Fermat replied immediately that it’s the product of 898423 and 112303, both of which are prime.

To this day, no one knows how he knew this. Has a powerful factoring technique been lost?

Traducido quedaría algo así:

Mersenne escribió una vez a Fermat preguntándole si 100895598169 era un número primo.

Fermat respondió inmediatamente que es el producto de 898423 por 112303, ambos primos.

A día de hoy nadie sabe cómo lo supo. ¿Se ha perdido una potente técnica de factorización?

Pues sí, al parecer no se sabe a ciencia cierta cómo factorizó ese número tan grande en tan poco tiempo. Lo que sí se conoce es un método de factorización ideado por Fermat, aunque yo dudo que fuera el que usó para este caso. Pasemos a explicarlo.

El método de factorización de Fermat

La cuestión es factorizar un cierto número n. La idea de Fermat es la siguiente:

Si n es igual a la diferencia de dos cuadrados, digamos n=x^2-y^2, entonces n puede factorizarse de forma muy sencilla de forma evidente: n=(x+y)(x-y).

Como x^2 debe ser mayor que n se tiene que x debe ser mayor que \sqrt{n}. A partir de ésto ya podemos adentrarnos en el método de factorización de Fermat:

Dado un número entero positivo n que queremos factorizar tomamos un entero positivo x mayor que \sqrt{n} (podemos calcular una aproximación de esa raíz cuadrada a ojo o con el método normal y después elegir x). Calculamos x^2 y le restamos n. Si obtenemos un cuadrado hemos terminado. Si no es así tomamos x+1, calculamos (x+1)^2, restamos n y si hemos obtenido un cuadrado se acaba. Procedemos de la misma forma hasta encontrar un cuadrado.

Vamos a ver un par de ejemplos de aplicación del método:

  1. Vamos a factorizar el número 13837. Su raíz cuadrada está entre 117 y 118. Tomamos x=118. Pero 118^2-13837=87, que no es un cuadrado. Tomamos ahora x=119. Ahora 119^2-13837=324=18^2. Por tanto despejando n=13837 de esta expresión tenemos su factorización: 13837=119^2-18^2=(119+18)(119-18)=137 \cdot 101
  2. Vamos ahora con un número más grande, el que utilizó Fermat para probar la efectividad de su método: 2027651281. Su raíz cuadrada está entre 45029 y 45030. Comenzamos con x=45030. Veamos qué resultados obtenemos:

    45030^2-2027651281=49619, que no es un cuadrado.
    45031^2-2027651281=139680, que no es un cuadrado.
    45032^2-2027651281=229743, que no es un cuadrado.
    45033^2-2027651281=319808, que no es un cuadrado.
    45034^2-2027651281=409875, que no es un cuadrado.
    45035^2-2027651281=499944, que no es un cuadrado.
    45036^2-2027651281=590015, que no es un cuadrado.
    45037^2-2027651281=680088, que no es un cuadrado.
    45038^2-2027651281=770163, que no es un cuadrado.
    45039^2-2027651281=860240, que no es un cuadrado.
    45040^2-2027651281=950319, que no es un cuadrado.
    45041^2-2027651281=1040400=1020^2.

    Por tanto ya tenemos la factorización:

    2027651281=45041^2-1020^2=(45041+1020)(45041-1020)=44021 \cdot 46061

Como podemos ver el método está muy bien si la diferencia entre los factores del número no es muy grande pero no es demasiado eficiente si los dos factores están muy alejados el uno del otro, ya que en ese caso la cantidad de cálculos que deberíamos realizar sería enorme. Esa es la razón por la que yo pienso que Fermat no usó este método para factorizar el número 100895598169 y me temo que siempre nos quedará la duda de qué método utilizó Fermat para realizar esta factorización. De todas formas el método es interesante ya que hasta en nuestros tiempos ha servido como motivación para la búsqueda de nuevos métodos de factorización.

Print Friendly, PDF & Email
4.3 3 votes
Article Rating

¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉