La factorización de Fermat

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.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

7 Comentarios

  1. Ni lo he intentado demostrarlo, pero ¿todo numero compuesto es factorizable por ese método?

    Publica una respuesta
  2. Daniel, los únicos números compuestos N que no se pueden descomponer en la forma N=(x+y)(x-y) son aquellos que dan un resto igual a 2 cuando se dividen por 4, o en otras palabras aquellos números de la forma N=2\cdot p siendo p un número impar. Esto es sencillo de ver, así como también es sencillo factorizar en la forma de Fermat cualquier otro número que no pertenezca a la clase anterior.

    Publica una respuesta
  3. Me pregunto si tiene algo que ver con la rapidez en la factorización el hecho de que 898423 = 8 × 112303 – 1.

    Publica una respuesta
  4. Vaya, curioso detalle. No sé si tendrá algo que ver, pero lo poquito que he encontrado por internet del tema habla de números relacionados con números primo de Mersenne, es decir, números promos de la forma 2^p-1 con p número primo.

    Desarrolla el tema por ahí, igual sacas alguna conclusión interesante.

    Publica una respuesta
    • Aquí una posible explicación a la factorización del número 100895598169 http://grafotutor.blogspot.com.es/2017/03/i-el-metodo-de-fermat-y-el-numero-100.html

      Copio y pego:

      En base a lo anterior, a continuación se describen las operaciones que podría haber efectuado Fermat para factorizar el número de Mersenne (Mn=100895598169).

      1. Comenzamos hallando los lados del triángulo con el valor más cercano posible a Mn, según esta expresión: (L² + L) / 2 = Mn

      2. Para despejar el valor de “L” resolvemos la ecuación de segundo grado L² + L – 2Mn = 0
      Obteniendo un valor para L = 449211,2500002

      3. Con la parte entera E = 449211 hallamos la superficie “S” de un nuevo triángulo.
      (E² + E) / 2 = 100895485866 valor de S.

      4. A continuación restamos el valor obtenido de la superficie del triángulo de lado E al número Mn para hallar “R”, el resto. Esto es Mn – S = 112303 valor del resto R.

      5. Por último dividimos el número Mn entre R, que resulta ser un número exacto con lo que probamos que el resto calculado es directamente un factor. 100895598169 / 112303 = 898423

      Por tanto la solución es 898423 • 112303 = 100895598169

      Publica una respuesta
  5. Fermat utilizó un método método muchísimo más eficiente que nunca publicó!

    Publica una respuesta

Trackbacks/Pingbacks

  1. Tiempo finito y logarítmico » El reto de Mersenne - [...] Witchcraft La factorización de Fermat [...]

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *