Sunday, January 17, 2016

Fermat and Factoring

As a Sunday reflection, this from the first volume of Greg Ross's Futility Closet:
"In 1643, Marin Mersenne wrote to Pierre de 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?"

[Additionally, be sure to check out my interview this morning at MathTango with Dr. Mircea Pitici, editor of "The Best Writing on Mathematics" series.]

1 comment:

Walt said...

It is not that surprising if we assume that Fermat used what we call Fermat's factoring method. Upon multiplying by the cofactor of 8 (and using difference of pronic numbers instead of squares since the number is now even) he would find this pair of factors on the first try. (I am assuming that taking the square root of a 12-digit number was feasible. Also, I have no idea how difficult it was at that time for him to prove the primality of the resulting 6-digit factors.)

In fact, 8 * 112303 = 898424 = 1 + 898423. This is a remarkable coincidence and makes me wonder if Mersenne used this relation to construct the problem in the first place.