Cracking Fermat Numbers

Fermat numbers have what mathematicians sometimes describe as a “beautiful mathematical form,” involving powers of 2. They were of interest 400 years ago and are now the subject of a wide-ranging worldwide computer search.

A Fermat number has the form 2²ⁿ + 1, where n is a whole number equal to or greater than 0. The first Fermat number, F0, is 2²⁰ + 1, or 3. The second Fermat number, F1, is 2²¹ + 1, or 5; the third is 2⁴ + 1, or 17; followed by 257, 65537, and 4294967297. What’s striking about the sequence is the rapidity with which the size of the numbers grows larger.

Written in binary notation, a Fermat number, Fn, consists of 2ⁿ – 1 zeroes between an initial and a final 1. So, 5 is 101, 17 is 10001, and 257 is 100000001.

In 1640, French mathematician Pierre de Fermat (1601–1665) conjectured that all such numbers are primes, based on the observation that the first five are prime numbers. In writing to Marin Mersenne (1588–1648), Fermat noted, “If I can determine the basic reason why 3, 5, 17, 257, 65537, . . . are prime numbers, I feel that I would find very interesting results, for I have already found marvelous things [along these lines] which I will tell you about later.”

In 1732, Leonhard Euler (1707–1783) discovered that 641 divides evenly into F5, refuting Fermat’s conjecture but setting another challenge: finding divisors of Fermat numbers.

Euler had shown that every divisor of a Fermat number Fn with n greater than 2 has the form k 2 ^{n + 1} + 1. In the case of F5, the divisor would be of the form 128k + 1. The first prime trial divisor is 257 (k = 2), but that doesn’t work. The second is 641 (k = 5), and it divides evenly into F5.

Thereafter, mathematicians continued to look for divisors of Fermat numbers, devising a variety of methods for identifying these scarce factors. It wasn’t easy to find them. By 1952, they had identified a total of only 16 divisors.

With the advent of computers and, recently, a concerted effort to use the spare processing power of computers around the world to test for divisors of Fermat numbers (see http://www.fermatsearch.org/), the search for factors has expanded considerably. As of Feb. 25, 212 Fermat numbers were known to be composite, and searchers had found a total of 245 prime factors. However, only F5 to F11 are completely factored.

One feature of the ongoing search is the race to set the record for the largest Fermat number known to be composite. On Feb. 21, John B. Cosgrove of St. Patrick’s College in Dublin, Ireland, found a new champion when he discovered that the Fermat number F2145351 is divisible by the 645817-digit prime number 3*2^2145353 + 1. The divisor itself is the fifth largest known prime number, and it is the largest that is not a Mersenne prime.

Cosgrove had played a part in the 1999 discovery of the previous record holder, F382447. In describing this number, he had noted, “Unimaginably large, its decimal digits cannot be written out in the entire universe.”

With that sort of antecedent, there would appear to be no superlatives left to describe the new, immensely larger composite Fermat number. Cosgrove made an attempt, however.

“The size of F2145351 is truly awesome,” he said. “To write out its decimal value—at four digits per inch in the horizontal and vertical directions—would require a square sheet of paper with side length exceeding 10³²²⁸⁸⁹ light-years.”

Awesome is putting it mildly!