Hace unos días veo este post en Futility Closet:
Mersenne once wrote to Fermat asking whether
were a prime number.
Fermat replied immediately that it’s the product of
and
, 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
era un número primo.
Fermat respondió inmediatamente que es el producto de
por
, 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 . La idea de Fermat es la siguiente:
Si es igual a la diferencia de dos cuadrados, digamos
, entonces
puede factorizarse de forma muy sencilla de forma evidente:
.
Como debe ser mayor que
se tiene que
debe ser mayor que
. A partir de ésto ya podemos adentrarnos en el método de factorización de Fermat:
Dado un número entero positivo
que queremos factorizar tomamos un entero positivo
mayor que
(podemos calcular una aproximación de esa raíz cuadrada a ojo o con el método normal y después elegir
). Calculamos
y le restamos
. Si obtenemos un cuadrado hemos terminado. Si no es así tomamos
, calculamos
, restamos
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:
- Vamos a factorizar el número
. Su raíz cuadrada está entre
y
. Tomamos
. Pero
, que no es un cuadrado. Tomamos ahora
. Ahora
. Por tanto despejando
de esta expresión tenemos su factorización:
- Vamos ahora con un número más grande, el que utilizó Fermat para probar la efectividad de su método:
. Su raíz cuadrada está entre
y
. Comenzamos con
. Veamos qué resultados obtenemos:
, que no es un cuadrado.
, que no es un cuadrado.
, que no es un cuadrado.
, que no es un cuadrado.
, que no es un cuadrado.
, que no es un cuadrado.
, que no es un cuadrado.
, que no es un cuadrado.
, que no es un cuadrado.
, que no es un cuadrado.
, que no es un cuadrado.
.
Por tanto ya tenemos la factorización:
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 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.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Ni lo he intentado demostrarlo, pero ¿todo numero compuesto es factorizable por ese método?
Daniel, los únicos números compuestos
que no se pueden descomponer en la forma
son aquellos que dan un resto igual a 2 cuando se dividen por 4, o en otras palabras aquellos números de la forma
siendo
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.
Me pregunto si tiene algo que ver con la rapidez en la factorización el hecho de que 898423 = 8 × 112303 – 1.
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
con
número primo.
Desarrolla el tema por ahí, igual sacas alguna conclusión interesante.
Si multiplicamos el número por 8 el nuevo número resultante se resuelve fácilmente por diferencia de cuadrados. Y ya teniendo los dos factores del nuevo número se divide el que sea par entre 8. Hablando del tema he creado un método un poco similar al de Fermat, donde me aconsejan publicarlo?
[…] Witchcraft La factorización de Fermat […]
112303 es una fecha..
Felices Reyes Magos,
Fernando.
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… Lee más »
Fermat utilizó un método método muchísimo más eficiente que nunca publicó!
En la carta original de Mersenne a Fermat primero le preguntaba por la relación entre un número formado por el producto de varios números y la suma de los divisores de este. Uno de esos números era el 100895598168. Al intentar dar solución al primer problema se encuentra la factorización.