One “long” multiplication problem
November 2, 2011 3 Comments
Here’s a simple question for you – What are the factors of 147,573,952,589,676,412,927? Impossible? Well, before you run off and find your calculator, would it help to mention that someone found its factors using only a pencil and paper? It’s true. On October 31, 1903, Frank Cole did just that. He factored the number 147,573,952,589,676,412,927 – with just a pencil and paper!
What makes the story so legendary is the way Cole revealed the factors. At a meeting of the American Mathematical Society, Cole presented his paper titled “On the factoring of large numbers.” Usually, when a mathematician presents a paper, he or she stands on a stage in front of a blackboard, lecturing to the audience about the particular topic of their paper. However, Cole’s lecture was different. He did not speak a single word. He simply went to the board, and began to calculate. On one side of the board, he calculated 267 - 1 = 147,573,952,589,676,412,927 by hand. Then he went to the other side of the board and worked out the product of 193,707,721 and 761,838,257,287, the factors of 147,573,952,589,676,412,927. After spending the silent hour working out the calculations, Cole simply turned around and went back to his seat, completely silent! The audience erupted into a standing ovation. Talk about making a dramatic presentation! Later, when asked how long it took him to find the factors, he responded by saying “three years of Sundays.”
So, why would anyone in their right mind take the time to factor such a big number you ask? Why this one? Why the number 267 - 1? It turns out that this number is related to something known as Mersenne Primes. First popularized by the French monk Marin Mersenne, primes of this form are generated using the formula 2p − 1 (where p is prime). For example: if p = 2, then 22 - 1 = 3 or if p = 5, then 25 - 1 = 31. And, as you know, both 5 and 31 are prime numbers.
I know what you are thinking – I thought it was impossible to have a formula that generates primes. Well, yes and no. While there is no formula that will generate ALL prime numbers, there are many formulas that generate some primes. Unfortunately, as with all prime formulas, even this formula doesn’t always work. For example, if p = 11, then 211 - 1 = 2047. 2047 is a composite number with factors 23 and 87.
So, why bother with a formula that inconsistently generates primes? Well, mathematicians are fun people. And, like most people, they are attracted to big things – like big prime numbers. Since this formula can generate some pretty massive numbers, the potential for monstrous size prime numbers exists. And, what’s better than massive prime numbers? Nothing! In fact, some mathematicians are so obsessed with really big primes that they have started an internet search for big primes called GIMPS – the Great Internet Mersenne Prime Search. If you go to this website, you can download a program to help out with the search! To date, there have been 47 Mersenne Primes discovered. The biggest, discovered on April 12, 2011, is a 12,837,064 digit number. (Click here to see the number.)
Like many of the massive numbers generated by Mersenne’s formula, 267 - 1 had the potential to be prime. However, no one was sure because there are no effective techniques for factoring large numbers. Finally, in 1876, Edouard Lucas made the first breakthrough by proving that this number could not be prime. However, he was unable to find its factors. Well, there is no greater enticement to a mathematician than a good mystery. So, the search began. And, thanks to Frank Cole, the mystery was solved on October 31, 1903.
For someone like me, a triumph like this, in the age of technology, should be celebrated! Well done!